<p>I learned that <span class="math-container">$\textsf{P/poly}$</span> is a class of problems computable by a polynomial-size circuit.
This class is considered a class of problems such that there exists a polynomial-time algorithm that is given a bitstring of <span class="math-container">$\textsf{poly}(n)$</span> length when the size of the input is <span class="math-container">$n$</span>.</p>
<p>On the other hand, <span class="math-container">$\textsf{NP}$</span> is a class of problems where for any problem, there exists a poly-time algorithm <span class="math-container">$M$</span> such that for every input <span class="math-container">$x$</span>, it is true iff there exists a bitstring <span class="math-container">$\alpha \in \{0,1\}^{\textsf{poly}(|x|)}$</span> such that <span class="math-container">$M(x,\alpha) = 1$</span>.</p>
<p>Then, does it hold <span class="math-container">$\textsf{P/poly} \subseteq \textsf{NP}$</span> ?</p>
<p>I have searched for such results but found only the results about the inverse relation <span class="math-container">$\textsf{NP} \subseteq \textsf{P/poly}$</span>.</p>
<p>Could you tell me the fact!!</p>
<p>I think that a bitstring of <span class="math-container">$\textsf{P/poly}$</span> is also used as the certification of <span class="math-container">$\textsf{NP}$</span>.</p>

CC BY-SA 4.0
2024-12-02T11:36:29.500Z
You may want to check the Complexity Zoo entry for P/poly: https://complexityzoo.net/Complexity_Zoo:P#ppoly
Evangelos Bampas
CC BY-SA 4.0
2024-12-02T11:59:10.160Z
This is not a research-level question, and should have been posted at https://cs.stackexchange.com . See e.g. https://cs.stackexchange.com/questions/126933/is-p-poly-known-to-be-in-re .
Emil Jeřábek
<cc.complexity-theory><complexity-classes><computational-mathematics>
Is P/poly included in NP?
The Black Calpis
# Is P/poly included in NP?

(Asked by: username_0 on 2024-12-02)

I learned that $\textsf{P/poly}$ is a class of problems computable by a polynomial-size circuit.
This class is considered a class of problems such that there exists a polynomial-time algorithm that is given a bitstring of $\textsf{poly}(n)$ length when the size of the input is $n$.

On the other hand, $\textsf{NP}$ is a class of problems where for any problem, there exists a poly-time algorithm $M$ such that for every input $x$, it is true iff there exists a bitstring $\alpha \in \{0,1\}^{\textsf{poly}(|x|)}$ such that $M(x,\alpha) = 1$.

Then, does it hold $\textsf{P/poly} \subseteq \textsf{NP}$ ?

I have searched for such results but found only the results about the inverse relation $\textsf{NP} \subseteq \textsf{P/poly}$.

Could you tell me the fact!!

I think that a bitstring of $\textsf{P/poly}$ is also used as the certification of $\textsf{NP}$.

**Tags:** cc.complexity-theory, complexity-classes, computational-mathematics
> **Comments:**
> **username_1**: You may want to check the Complexity Zoo entry for P/poly: https://complexityzoo.net/Complexity_Zoo:P#ppoly  
> **username_2**: This is not a research-level question, and should have been posted at https://cs.stackexchange.com . See e.g. https://cs.stackexchange.com/questions/126933/is-p-poly-known-to-be-in-re .  

---

## 0 answers

