Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

The Difference and Truth-Table Hierarchies for NP

Johannes Köbler, Uwe Schöning, and Klaus Wagner


Two hierarchies of complexity classes are defined. Both, the difference hierarchy and the truth-table hierarchy for NP are located between NP as bottom class and P(NP). We give examples for complete sets in both hierarchies and investigate their interrelationships. It turns out that the "omega-jump" of the truth-table hierarchy depends on the encodings of Boolean functions that we use.