Generally, for these tasks when we say "humans can solve them" then people are not solving the same problem; they're trying (and succeeding) to find a good solu

Generally, for these tasks when we say "humans can solve them" then people are not solving the same problem; they're trying (and succeeding) to find a good solution (where various heuristics work), and often for most, realistic cases only, while the theoretical problem is to have a process that will certainly find a solution that's guaranteed to be the absolute best possible even in weird degenerate cases, and that simply is a very different, much harder problem. E.g. halting problem, traveling salesman, etc, etc have people commenting that "but humans can solve them" in this manner.