Autoreducibility, Mitoticity, and Immunity Christian Glaßer∗, Mitsunori Ogihara†, A. Pavan‡, Alan L. Selman§, Liyu Zhang¶ December 27, 2004 Abstract We show the following results regarding complete sets.

Source URL: www.cse.buffalo.edu

• Complexity classes
• Structural complexity theory
• Mathematical optimization
• Probabilistic complexity theory
• NP
• PP
• Polynomial hierarchy
• PSPACE-complete
• P versus NP problem
• Theoretical computer science
• Computational complexity theory
• Applied mathematics