Complex suggests the unavoidable result of a necessary combining and does not imply a fault or failure (e.g. a complex recipe). Complicated applies to what offers great difficulty in understanding, solving, or explaining (e.g. complicated legal procedures).

(Complex can also be a noun.)

So, complicated = unnecessarily complex.