  We consider problems that can be solved by asking certain queries. The
deterministic query complexity $D(P)$ of a problem $P$ is the smallest number
of queries needed to ask in order to find the solution (in the worst case),
while the non-deterministic query complexity $D_0(P)$ is the smallest number of
queries needed to ask, in case we know the solution, to prove that it is indeed
the solution (in the worst case). Equivalently, $D(P)$ is the largest number of
queries needed to find the solution in case an Adversary is answering the
queries, while $D_0(P)$ is the largest number of queries needed to find the
solution in case an Adversary chooses the input. We define a series of
quantities between these two values, $D_k(P)$ is the largest number of queries
needed to find the solution in case an Adversary chooses the input, and answers
the queries, but he can change the input at most $k$ times. We give bounds on
$D_k(P)$ for various problems $P$.
