Complex is used in the sense that you have to consider multiple things (such as constraints, logic, etc) in order to come up with a working solution. You cannot

Complex is used in the sense that you have to consider multiple things (such as constraints, logic, etc) in order to come up with a working solution. You cannot really escape from a complex problem because you have to satisfy all of its needs. On the other hand, 'complicated' here is probably meant in the sense that you have a solution for your problem, but that might not be the simplest solution to the problem. In other words, you have satisfied all of the problem's needs but the solution itself is going to be hard to understand for anyone other than the person implementing it. You generally want to avoid such situations.