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

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

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

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