Should neural nets be deeper the more complex the learning problem is?
Deeper models can have advantages (in certain cases)

Most people will answer "yes" to your question, see e.g. Why are neural networks becoming deeper, but not wider? and Why do deep neural networks work well?. 

In fact, there are cases where deep neural networks have certain advantages compared to shallow ones. For example, see the following papers 


The Power of Depth for Feedforward Neural Networks (2016) by Ronen Eldan and Ohad Shamir
Benefits of depth in neural networks (2016) by Matus Telgarsky.
Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks (2017) by Safran and Shamir
Optimal approximation of piecewise smooth functions using deep ReLU neural networks (2018) by Petersen and Voigtlaender


What about the width?

The following papers may be relevant


Wide Residual Networks (2017) by Sergey Zagoruyko and Nikos Komodakis
The Expressive Power of Neural Networks: A View from the Width (2017) by Zhou Lu et al.


Bigger models have bigger capacity but also have disadvantages

Vladimir Vapnik (co-inventor of VC theory and SVMs, and one of the most influential contributors to learning theory), who is not a fan of neural networks, will probably tell you that you should look for the smallest model (set of functions) that is consistent with your data (i.e. an admissible set of functions).  

For example, watch this podcast Vladimir Vapnik: Statistical Learning | Artificial Intelligence (AI) Podcast (2018), where he says this. His new learning theory framework based on statistical invariants and predicates can be found in the paper Rethinking statistical learning theory: learning using statistical invariants (2019). You should also read "Learning Has Just Started" – an interview with Prof. Vladimir Vapnik (2014).

Bigger models have a bigger capacity (i.e. a bigger VC dimension), which means that you will more likely overfit the training data, i.e., the model may not really be able to generalize to unseen data. So, in order not to overfit, models with more parameters (and thus capacity) will also require more data. You should also ask yourself why people use regularisation techniques. 

In practice, models that achieve state-of-the-art performance can be very deep, but they are also computationally inefficient to train and they require huge amounts of training data (either manually labeled or automatically generated). 

Moreover, there are many other technical complications with deeper neural networks, for example, problems such as the vanishing (and exploding) gradient problem. 

Complex tasks may not require bigger models

Some people will tell you that you require deep models because, empirically, some deep models have achieved state-of-the-art results, but that's probably because we haven't found cleverer and more efficient ways of solving these problems. 

Therefore, I would not say that "complex tasks" (whatever the definition is) necessarily require deeper or, in general, bigger models. While designing our models, it may be a good idea to always keep in mind principles like Occam's razor!

A side note

As a side note, I think that more people should focus more on the mathematical aspects of machine learning, i.e. computational and statistical learning theory. There are too many practitioners, who don't really understand the underlying learning theory, and too few theorists, and the progress could soon stagnate because of a lack of understanding of the underlying mathematical concepts.

To give you a more concrete idea of the current mentality of the deep learning community, in this lesson, a person like Ilya Sutskever, who is considered an "important and leading" researcher in deep learning, talks about NP-complete problems as if he doesn't really know what he's talking about. NP-complete problems aren't just "hard problems". NP-completeness has a very specific definition in computational complexity theory!