Between the deterministic and non-deterministic query complexity

Dániel Gerbner

We consider problems that can be solved by asking certain queries. The deterministic query complexity $D(P,n)$ of a problem $P$ is the smallest number of queries needed to ask in o…