Skip to main content
deleted 1 character in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

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

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

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

Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

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