Complexity Classes

• mémoire
• exposé

Complexity Classes Eric Allender Rutgers University Michael C. Loui University of Illinois at Urbana-Champaign Kenneth W. Regan State University of New York at Buffalo 1 Introduction The purposes of complexity theory are to ascertain the amount of computational resources required to solve important computational problems, and to classify problems according to their diculty. The resource most often discussed is computational time, although memory (space) and circuitry (or hardware) have also been studied.

• computation path
• unwritten cells
• upper bound on deterministic time
• class of languages
• diagonalization technique
• complexity theory
• polynomial-time
• polynomial time
• machines
• space
• time