Abstract 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.