After a brief review of the basic notions of complexity theory, some results are presented suggesting that the interaction between complexity theory and artificial intelligence has already been useful and will increase. The paper seems to be intended as an introduction, but is perhaps too short to convince those readers having little background in complexity theory.