What is the difference between "complicated" and "complex"?

Complex is used to refer to the level of components in a system. If a problem is complex, it means that it has many components. Complexity does not evoke difficulty.

On the other hand, complicated refers to a high level of difficulty. If a problem is complicated, there might be or might not be many parts but it will certainly take a lot of hard work to solve.

In the Zen of Python, we have an aphorism

Simple is better than complex.
Complex is better than complicated.

It's a handy guideline when you are designing something.

One subtle distinction between the two is that where the complexity was in some sense introduced, it is probably more common to use "complicated" than "complex." For example,

The instructions were way too complicated.

It is of course true that the instructions were also complex, but the silent implication in using "complicated," the past participle of "to complicate," is that somebody caused the complexity, as opposed to it being inherent in the subject. As a result, "complicated" sometimes has a negative connotation, effectively meaning "unnecessarily complex."

Quantum mechanics is an inherently complex subject, but the textbook was an even tougher slog because of the author's complicated explanations.

However, as others have said, there is a large overlap in the use of the two words.

Also, the idiomatic retort "It's complicated" is a sort of defense or apology for not being able to give a simple, and often expected, answer:

"What were you doing with Teresa? Don't you love your wife?"

"Yes, but ... it's complicated."

These words have a really large overlap, but they each have some distinct uses.

Complicated can refer to things that are difficult to explain because they are unclear rather than because they have a lot of parts. For example, Facebook's "It's complicated" relationship status could refer to a relationship that is one-to-one, but not well-defined.

Complex also has some technical meanings, as in "Complexity theory". This is related to the idea that the behavior of a system cannot be fully understood even if the parts are understood. This meaning is much more specific than what is conveyed by "complicated".