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

Artificial Intelligence aims to study this kind of problems, there are 3 classes of problems  : P, NP and NP-Complete.
Polynomial, Non Polynomial and  NP-Complete. NP-C are very difficult and the Polynomial class are decidable and you can find an algorithm (effective one) to solve them.

anonymous · Answer

No. It means that AI systems should avoid trying to solve intractable problems.
Usually,This means they can only approximate optimal behavior. Notice that humans don’t solve NP-Complete problems either. Sometimes they are good at solving specific instances with a lot of structure, perhaps with the aid of background knowledge.AI systems should attempt to do the same.