Beyond P and NP – Computational Complexity Hierarchy
Frank Ford
The holy grail of theoretical computer science is the solution of the P=NP question. Researchers have defined many other classes of problems using time and space and even types of proofs. This talk will describe some of these classes and discuss their relationships. A common picture of these classes is shown below. If time permits, we will try to discuss the class IP which is often defined in terms of Arthur and Merlin trying to verify proofs.
