There are well-known classes of problems that are intractably difficult for computers,
and other classes that are provably undecidable by any computer. Does this mean that AI is
impossible?

Question

There are well-known classes of problems that are intractably difficult for computers,
and other classes that are provably undecidable by any computer. Does this mean that AI is
impossible?

anonymous · Answer

Why would one follow from the other. A large set of AI problems are decidable and even tractable.

anonymous · Answer

By intractably difficult problems you are likely referring to NP-complete problems. However, even for these problems there in many cases approximations (algorithms for finding approximate solutions) which are tractable.

anonymous · Answer

By approximations I mean deciders for relaxed forms of NP-complete decision problems.

anonymous · Answer

"I, for one, welcome our new computer overlords." - Ken Jennings' tongue in cheek lamentation after being defeated by Watson, an IBM computer, on the game show Jeopardy.