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.


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.

| improve this answer | |
  • 1
    $\begingroup$ So, there's no known statistical limitations either? I wasn't expecting the answer to be "AI stops at PSPACE" but since most AI is statistical in nature, it seems plausible that if we can prove that most instances are "statistically unrepresentative" in some sense, then that would be an issue for AI. $\endgroup$ – Stella Biderman Sep 6 '18 at 20:35
  • 1
    $\begingroup$ We have some "No-Go" theorems for statistical learning, but they tend to be related to the philosophical conundrum that "we aren't sure if the future is like the past" (see, e.g. Hume, No Free Lunch Theorem). They say that for any statistical learning method, hard problems exist. Again though, in practice this just means you pick different techniques for different problems. There are some problems we can't solve at all, but usually these aren't "problems" in the traditional sense. For example, AI can't predict the future from the stars, but neither can any intelligent entity. $\endgroup$ – John Doucette Sep 6 '18 at 22:47
  • $\begingroup$ I think this answer is a little bit misleading for several reasons. Current language systems (e.g. machine translation), even though perform better than previous ones, still perform poorly compared to (professional) humans. Also, language understanding is still believed to be a hard problem (AI-complete) because of the possibly infinite combinations. Finally, there is some work related to the definition of "hard" for an AI (that is, AI-complete problems, like natural language understanding). Finally, NP-hard problems are really hard. The solutions we obtain are usually approximations anyway. $\endgroup$ – nbro Jul 7 '19 at 14:07
  • $\begingroup$ @nbro I agree that NP-Hard problems are hard in theory, but they just aren't that hard in practice. See, e.g. Thomas Sandholm's career as an example. They aren't a reliable measure of intelligence, because most instances are easy to solve (exactly), and the other ones we can get high quality approximations for quickly in most cases. The AI-complete literature is new to me though. Do you have a suggested reading on this I could use to augment the answer? $\endgroup$ – John Doucette Jul 7 '19 at 21:42
  • $\begingroup$ @JohnDoucette AFAIK, some NP-complete problems, like the TSP, can be (approximately) solved efficiently in practice because there are algorithms that have been developed "specifically" for that problem (in the case of TSP, e.g. ant colony optimization algorithms). However, these are still combinatorial problems, so as the size of the problem increases, even approximate solutions can become intractable. Regarding the AI-complete expression, have a look at these answers I had given a few weeks ago: ai.stackexchange.com/a/12147/2444 and ai.stackexchange.com/a/12978/2444. $\endgroup$ – nbro Jul 7 '19 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.