0
$\begingroup$

The answer is yes, NP/poly is defined as the class of problems solvable in polynomial time by a non-deterministic Turing machine that has access to a polynomial-bounded advice function--the advice function only adds power; however, I'm having a hard time understanding NP/poly's containment of NP from the angle of the definition below of NP/poly:

A nondeterministic circuit has two inputs x,y. The circuit C accepts x iff there exists y such that C(x,y) = 1. The size of the circuit is measured as a function of |x|. NP/poly is the set of languages decided by polynomial size non-deterministic circuits.

A nondeterministic Turing machine has two inputs w,c. A verifier V accepts w iff there exists a certificate c such that V(w,c) = 1. The length of computation is measured as a function of |w|. NP is the set of languages decided by a nondeterministic Turing machine that runs in polynomial time.

From the verifier angle, for a couple reasons it is hard to see how a single circuit of poly size could implement a verifier for an NP problem for all the words of a given length.

  1. For example. let's say an NP language has an exponential number of yes instances of a given length all with various certificates. Let's say we consider those certificates that are descriptions of the accepting branches of a non-deterministic Turing machine that correctly decide each w of the given length--how could a single poly size circuit simulate all these (possibly exponential number of) c's (solution paths) on their respective w's to see if the verifier works?

  2. A circuit can only have a single size input and for each size of input there is only one circuit in the circuit family; yet, for a given word w of length b there are an infinte number of c's that are poly|w| that are potential certificates--how can the single circuit for inputs of length b accept on all the different certificates for the w's of length b when their lengths are variable?

Looking for some help on how I'm thinking about this wrong, thank you!

$\endgroup$
17
  • 2
    $\begingroup$ The last paragraph is hard to understand. Please try to reformat it (at least split this into bullet list: one item per issue). there are an infinte number of c's that are poly|w| that are potential certificates for w's of length b--how can a single circuit ... accept on all the different certificates for the w's - you don't care about all of them. It suffices to know that there exists a certificate with size polynomial of input size. For each $x$. there exists a certificate of size $p(|x|)$: the input layer of the circuit will have size $|x| + p(|x|)$. This way, it'll include some cert. $\endgroup$ – Dmitry Nov 24 '20 at 22:19
  • 1
    $\begingroup$ @Dmitry cleaned it up a bit--thank you--addressing your comment in relation to the question: does that mean there is a poly size circuit for every length of word +certificate pair? If so, some of those circuits might need to accept |𝑥|+𝑝(|𝑥|) as well as another |y|+𝑝(|y|) if |y|+𝑝(|y|)=|𝑥|+𝑝(|𝑥|). Cases like this seem like they could present a problem, no? How can you predict when this is going to happen? $\endgroup$ – DeeDee Nov 25 '20 at 2:38
  • 1
    $\begingroup$ The verifier $V$ is a deterministic Turing machine. There is only one computation branch. $\endgroup$ – Yuval Filmus Nov 25 '20 at 8:31
  • 1
    $\begingroup$ By padding witnesses, you can assume that their size only depends on the input size. $\endgroup$ – Yuval Filmus Nov 25 '20 at 8:32
  • 1
    $\begingroup$ No. You have a different circuit for each $|x|$. $\endgroup$ – Yuval Filmus Nov 25 '20 at 14:32
2
$\begingroup$

A language $L$ is in $\mathsf{NP}$ if there exists a polynomial $p$ and a deterministic Turing machine $T$, running in polynomial time, such that:

$x \in L$ if and only if there exists $y$ of length $p(|x|)$ such that $T(x,y) = 1$.

Usually we assume that $|y| \leq p(|x|)$, but we can get this version using a simple padding argument, which slightly increases $p$. For example, we could encode $y$ as follows: $0^{p(|x|)-|y|}1y$. This always has length $p(|x|)+1$. (We also obtain a new witness $0^{p(|x|)+1}$ which corresponds to no $y$, which $T$ can just immediately reject.)

For every $n$, we can construct a polynomial size circuit $C_n$ on $n + p(n)$ inputs such that for every $x$ of length $n$ and $y$ of length $p(n)$, we have $C_n(x,y) = T(x,y)$. A similar construction appears in Cook's theorem, for example. This shows that $\mathsf{NP} \subseteq \mathsf{NP/{poly}}$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.