Manindra Agrawal, Richard Beigel, Thomas Thierauf

The classes of languages accepted by nondeterministic polynomial-time

Turing machines (NP machines, in short) that have restricted access to

an NP oracle --- the machines can ask k queries to the NP oracle and

the answer they receive is the number of queries ...
more >>>

Richard Chang

This paper introduces a new model of computation for describing the

complexity of NP-approximation problems. The results show that the

complexity of NP-approximation problems can be characterized by classes of

multi-valued functions computed by nondeterministic polynomial time Turing

machines with a bounded number of oracle queries to an NP-complete

language. ...
more >>>

Tobias Riege, Jörg Rothe

We prove that the exact versions of the domatic number problem are complete

for the levels of the boolean hierarchy over NP. The domatic number

problem, which arises in the area of computer networks, is the problem of

partitioning a given graph into a maximum number ...
more >>>

Tobias Riege, Jörg Rothe

This paper surveys some of the work that was inspired by Wagner's general technique to prove completeness in the levels of the boolean hierarchy over NP and some related results. In particular, we show that it is DP-complete to decide whether or not a given graph can be colored with ... more >>>