Polynomial and Exponential Complexity

Artificial intelligence is used whenever problems need to be solved that humans can understand and define, but which they cannot solve due to the complexity of the problem. A distinction is made between two basic forms of complexity: polynomial and exponential complexity. A typical example of exponential complexity is a family tree: every person has two parents, four grandparents, and eight great-grandparents. This means that such a family tree quickly becomes wider and wider toward the top. An example of polynomial complexity are search problems, the search for a particular book in a bookcase, etc. A number of combinatorial problems are given as examples of the different complexities, and it is shown how to overcome these difficulties.