3
$\begingroup$

I'd like to prove that, with respect to some adversarial oracle $O$, $coNP^O \not\subseteq NP/poly^O$. I was thinking of using $\textsf{UNSAT}$ for this and to build my oracle as follows: $O$ will "hold" a bunch of boolean formulas (or truth tables) and queries to the oracle will specify an index $x$ of a particular formula $\phi_x$ and an assignment $y$ of the variables in that formula. The oracle responds with $1$ if the formula is $\textbf{not}$ satisfied by that assignment (i.e. $\phi_x(y) = 0$) and $0$ otherwise. For simplicity I'll assume that for every $n$ we consider $2^n$ formulas each having exactly $n$ variables (so $x,y \in \{0,1\}^n$). That way the index for the formula and the assignment are both $n$-bit strings. So:

Input to oracle: $\langle x y \rangle$, where $|x|=|y|=n$

Output: $O(\langle x y \rangle)= 1 \oplus \phi_x(y)$, which is $1$ if the formula is not satisfied by the assignment $y$ and $0$ otherwise

I can then consider the language $UNSAT(O) = \{ 0^nx | \forall y \in \{0,1\}^n, O(\langle x y \rangle) = 1 \}$.

Clearly this language is in $coNP^O$, but I'm not sure how to show that it's not in $NP/poly^O$. It's relatively easy to show that it's not in $NP^O$ through diagonalization (enumerate all $NP^O$ machines, for each one consider some input formula which is unsatisfiable; if the machine rejects then it's wrong and we move on, if it accepts that means that there is some accepting path making polynomially many queries to the oracle; keep the answers to those queries the same, while changing the formula so that it's satisfiable).

The intuition is that because we are considering a new formula for each $x$, there are $2^n$ formulas for the same input length $2n$. However, the advice $a$ is the same for all of these and is only polynomial in size so it can't be of much help for exponentially many inputs. And therefore (big leap) if an $NP$ machine with polynomial advice could solve this, then an $NP$ machine without advice also could and that would lead to a contradiction. Unfortunately I haven't been able to formalize that intuition. I guess the idea is to show that I can always consider $2^n$ formulas such that there is no advice of polynomial length that can make the $NP$ machine decide correctly on all of them. Of course, there are $2^{poly(n)}$ possible advice strings and it's unclear to me how I can rule out all of them.

In fact, I'm not even sure how to show that $coNP^O \not\subseteq P/poly^O$.

(I'm aware that in the unrelativized setting, if $coNP \subseteq NP/poly$ the polynomial hierarchy collapses at the 3rd level, but I'm not sure that helps and in any case I'd like to operate only on these complexity classes)

$\endgroup$
  • $\begingroup$ One thing to try here is "diagonalizing against the majority". On the first formula $x$, you try to diagonalize against at least half of the advised NP machines. On the next formula, you do the same thing, but only focus on diagonalizing against a majority of the advised NP machines that survived the previous round. And so on, until nothing is left. To rule out $2^{f(n)}$ machines, you only need $f(n)+1$ choices of $x$. $\endgroup$ – Andrew Morgan Oct 9 '16 at 14:14
  • 1
    $\begingroup$ Also, this fact that "if coNP is in NP/poly, then PH collapses" relativizes, so you could let $O$ be an oracle relative to which PH doesn't collapse so far. $\endgroup$ – Andrew Morgan Oct 9 '16 at 14:21
  • $\begingroup$ Thanks for the reply. That's what I was thinking of doing as well. However, the problem is the following: suppose that I consider formula $\phi_x$ and make it unsatisfiable. I then look at what the machine does for the different possible advices (I'll refer to these as different machines). If most of them reject, then they will be wrong and I can move on. If most of them accept, I need to turn my formula into a satisfiable one while keeping these machines accepting. Accepting means that for each one there is at least one polynomial sized path which is accepting. $\endgroup$ – user1033363 Oct 9 '16 at 19:41
  • $\begingroup$ On these paths, the machine can query polynomially many assignments. When I was dealing with only one machine that was ok, because my truth table for a formula is of size $2^n$ and I can easily keep polynomially many entries the same, while changing the rest to make the formula satisfiable. But in this case each accepting machine is adding poly many constraints on my truth table. The number of possible machines/advices is $2^{poly(n)}$, so half of them is still a $2^{poly(n)}$ which can easily be much larger than $2^n$. $\endgroup$ – user1033363 Oct 9 '16 at 19:43
  • $\begingroup$ (assuming, in the worst case, that each machine makes different queries than the other ones) $\endgroup$ – user1033363 Oct 9 '16 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.