What does "hard for AI" look like?

Question

In theoretical computer science, there is a massive categorization of the difficulty of various computational problems in terms of their asymptotic worst-time computational complexity. There doesn't seem to be any analogous analysis of what problems are "hard for AI" or even "impossible for AI." This is in some sense quite reasonable, because most research is focused on what can be solved. I'm interested in the opposite. What I do need to prove about a problem to prove that it is "not reasonably solvable" by AI?

Many papers say something along the lines of

AI allows us to find real-world solutions to real-world instances of NP-complete problems.

Is there a theoretical, principled reason for saying this instead of "... PSPACE-complete problems"? Is there some sense in which AI doesn't work on PSPACE-complete, or EXPTIME-complete, or Turing complete problems?

My idea answer would be a reference to a paper that shows AI cannot be used to solve a particular kind of problem based on theoretical or statistical reasoning. Any answer exhibiting and justifying a benchmark for "too hard for AI" would be fine though (bonus points if the benchmark has a connection to complexity and computability theory).

If this question doesn't have an answer in general, answers about specific techniques would also be interesting to me.

Answer 1

Nice Question!

This is a perennial topic of discussion among AI researchers. The short answer is "we don't really know which topics are hard in general, but we do know which we haven't got good techniques for yet."

Let's start by explaining why AI is not concerned with notions of computational complexity like NP-Completeness. AI researchers figured out in the 90's that most problems that are computationally hard in theory aren't actually hard in practice at all! For example, Boolean Satisfiability, the canonical NP-Hard problem, is known to have hard instances, but in practice, these almost never show up. Even when they do, we can usually get good approximate solutions with minimal computation time. Since many AI problems are reducible to SAT, whole areas of the field just use these approximation techniques and solvers. There's a good, if a bit old, survey here. Since 2008, things have only gotten better. Basically, NP-Hard stuff just isn't that hard. Worst-case complexity is therefore probably the wrong tool to guess at which problems are hard for AI.

At the other end of the scale, we have subjective complexity based on things like how "large" the problem is. This has proven to be pretty unreliable. One example is Go, which I was told would "never be solved by AI" as late as 2010. Clearly, we were completely wrong. We just didn't know which techniques to use yet. Another example is language. Rule-based AI'ers tried at it for decades with minimal success. Probabilistic methods have achieved essentially human-level performance in less time. If you asked a researcher in the 1970s if language was hard for AI, they'd have said yes, but they'd have been wrong. This has been closely related to the advances in computing hardware: techniques that seemed wasteful and slow 40 years ago are now entirely practical. Sometimes they turn out to solve problems really well.

Part of this ties into the issue that AI'ers don't really know or agree on what intelligence is, or what it means to solve a problem. Some AI'ers maintain that language really is hard, and that the systems we use now aren't really solving language, they're just making blind guesses that happen to be right a lot. Under that view, language is still hard. Fodor was a strong proponent of this view in the past, and his writings are a good place to read about it, but I've still heard people espouse views like this at AI conferences as recently as 2015.

Something this usually considered hard right now is making a good general intelligence, that integrates knowledge across many domains and could plausibly pass something like the Turing test. Yet, there has been some progress here (look at virtual assistants), and some AI'ers reckon this might not be as hard as we thought either.

So, basically, we don't know what's hard because we don't know when someone will come up with a new exciting technique that solves problems previously thought to be hard, we know that worst-case complexity isn't a good measurement system for "intelligence" requirements, and we don't know what intelligence really is.