alt Hacker NewsComplex = a problem that's inherently difficult to solve due to its fundamental nature. Time is a great example.
Complicated = a solution that's difficult to understand due to a convoluted implementation. These can be simplified.
In other words, the difference is whether the difficulty is inherent to the problem space (complex) versus inflicted by a solution (complicated).
If complex only refers to inherent complexity (and not accidental complexity and whatever other attributes were used by people before) then how is "simple is better than complex" to be read? If complex is inherent to the problem, does it mean "solve a different problem"?