The Difference and Truth-Table Hierarchies for NP
Johannes Köbler, Uwe Schöning, and Klaus Wagner
Abstract:
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.