The complexity of a problem doesn't tell you anything at all about the complexity of a solution. Many problems that we face are "angels dancing on pins"-type problems, where the only 'complexity' involved is all the hoops you have to jump through to defend a flawed perspective. And on the other hand we have these coin-flip-prediction problems that only demand one bit of information, but are completely intractable by our most advanced methods.

Complexity is not a useful way to think about problem solving. Nobody solves complex problems.