Simplicity is highly abused term. It is now synonymous with good and consequently complexity now stands for bad. Making such a statement is usually complex. It needs time, understanding of the subject. But often, i
t is very easy to judge simplicity and complexity. If you understood it is simple, if you don't it is complex. The relative frame becomes the "person" not the problem/solution space. What takes real thinking is judging if something is "appropriate". It comes only after you understand the problem and the solution so well that you can judge if the solution is appropriate.
What makes something simple or complex?
Lets talk physics for a while. Earth is the center of the universe and sun revolves around the earth. That is simple. Every child thinks that unless told by teachers or parents. Problem is, simplicity doesn't helps when you are sailing oceans or launching a satellite. Consider motion. Classical mechanics is simple. It is still heavily used. Relativity is a bit complex, just add the observer and how he observes to the equation. That is necessary if you are dealing with small particles, moving close to speed of light. There is nothing wrong with classical mechanics, it is simple and appropriate for lot of things.
Solutions are simple or complex, depending upon the levels of abstraction used in understanding the problems. We won't be able to build any building if we start at atomic level. Recipes at atomic level will be useless. The unified theory of everything is obviously simple in terms of its constructs but becomes very complex to deal with high level problems. So
in some sense complexity arises from simplicity - simplicity of abstractions. It can come from complexity of abstractions too, but that is obvious. Take a look at nginx module architecture. It is simple. Call all modules to find if someone will handle this request and then let it handle it. Problem is writing the handler. Nginix modules need to do everything themselves and cannot uses code from other modules because the architecture encourages isolation. So we have chunked encoding implemented in basic http module, file upload module, the upstream module, etc. I guess the same needs to be done for compression, caching, etc. Simple architecture, complex modules.
The opposite is also true. Complexity also leads to simplicity. Understanding complexity needs lots of thinking. Finding out how things are working, why are things the way they are. What are the assumptions. This knowledge is at the heart of seeing simple way of doing the same things. Good needs bad to differentiate. Simplicity doesn't occurs in isolation. It needs complexity as a yard stick.
When Einstein said "Everything should be made as simple as possible", he also added, "but not simpler". The question is not simple solution vs complex solution, but appropriate level of simplicity or appropriate level of complexity or put appropriately - finding the appropriate solution.