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.

I am forced by my nature to add a more pedantic answer to the list. The content of this answer does not reflect my personal opinion, nor does it reflect common usage, but it does explain why the two words are not precisely interchangeable in all circumstances.

Complexity is intrinsic. Something is complex if it involves a lot of [metaphorical] moving parts even when considered as a Platonic ideal.

Complication is extrinsic. Something is complicated by external influences, or because of external influences.

Pedantically, something can be complex without being complicated, or complex because it is complicated. (Things are rarely complicated without also being complex.) In realms where precision is important, there is often a distinct division between the terms. In medicine, for instance, a broken bone may be described as a complex fracture because the fracture is complicated by breaking the skin, inviting the risk of infection.

Here endeth the pedantry.

In common use, complex is more usually used in a technical sense. Complicated is more likely to appear in everyday language among the general population since most complexity in everyday life is complicated in some way. Complicated may not always be precisely correct, but most people don't spend their lives with a dictionary in one hand and a thesaurus in the other looking for le seul mot juste -- they already have a word that means what they want to say.

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."

You can use them interchangeably.

Complicated: consisting of a lot of different parts or details and therefore difficult to understand. Examples:

1- The rules of the game seemed very complicated.

2- I didn’t realize programming the VCR would be so complicated.

3- The brain is like a very powerful, very complicated computer.

4- a complicated issue

Complex: a complex process, relationship etc is difficult to understand because it has a lot of parts that are all connected in different ways. Examples: