# Is NP in NP/Poly?

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?

• 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. – user114966 Nov 24 '20 at 22:19
• @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? – DeeDee Nov 25 '20 at 2:38
• The verifier $V$ is a deterministic Turing machine. There is only one computation branch. – Yuval Filmus Nov 25 '20 at 8:31
• By padding witnesses, you can assume that their size only depends on the input size. – Yuval Filmus Nov 25 '20 at 8:32
• No. You have a different circuit for each $|x|$. – Yuval Filmus Nov 25 '20 at 14:32

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}}$$.