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?

No. It is not impossible to understand and make this algorithm a success. It may only take a longer duration to reach success but it does not that it is impossible. Problems may become more difficult to understand and debug but there is enough time, duration, resources and support, the algorithm can be developed.