2
$\begingroup$

There is a definition for NP shown below. Could anyone please explain why "By restricting the definition of NP to witness strings of length zero, we capture the same problems as those in P."?

Definition 2.1 (The Class NP). A language $\mathcal{L}$ is in the class NP if there exists a polynomial time algorithm $\mathcal{R}_\mathcal{L}$ such that

$$ \mathcal{L} = \{ x \mid \exists w, |w| = \text{poly}(|x|) \land \mathcal{R}_\mathcal{L}(x, w) = 1 \}. $$

By restricting the definition of NP to witness strings of length zero, we capture the same problems as those in P. While the class P is clearly included in NP, finding whether NP is included in P is one of the most important open problems in computer science.

You can find this paper through the link below: https://www.di.ens.fr/~nitulesc/files/Survey-SNARKs.pdf

$\endgroup$
1
  • $\begingroup$ Which direction of the equivalence are you confused about? That all NP problems with a fixed empty witness are in P? Or, all problems in P are in the set of NP problems with a fixed empty witness? $\endgroup$
    – poncho
    Commented Jun 13 at 8:13

1 Answer 1

2
$\begingroup$

The polynomial time algorithm $\mathcal{R}_{\mathcal{L}}$ serves as a verifier, certifying that $x \in \mathcal{L}$ through the witness/proof $w$. For example, to show that a formula $\phi(x_1, \dots, x_n) \in \mathsf{SAT}$ (Satisfiability problem), the witness is an assignment $(b_1, \dots, b_n)$ such that $\phi(b_1, \dots, b_n) = 1$. Using the witness, the verifier $\mathcal{R}_{\mathsf{SAT}}$ outputs $\phi(b_1, \dots, b_n)$. Notice that if $\phi(x_1, \dots, x_n) \notin \mathsf{SAT}$, then for all assignments $(b_1, \dots, b_n)$, $\mathcal{R}_{\mathsf{SAT}}$ would output 0. Observe that the verification requires polynomial time in the presence of the witness/proof, yet obtaining such a witness is difficult for languages in $\mathsf{NP} \setminus \mathsf{P}$.

According to the definition of $\mathsf{P}$, a language $\mathcal{L} \in \mathsf{P}$ if there exists a polynomial-time algorithm $\mathcal{A}$ that can determine if $x \in \mathcal{L}$ or not. Therefore, in the above definition, the polynomial time verifier can decide if $x \in \mathcal{L}$ without using a witness/proof. In other words $\mathcal{R}_{\mathcal{L}}$ can be the algorithm $\mathcal{A}$. Since $\mathcal{A}$ is the polynomial time algorithm that solves $\mathcal{L}$, it takes as input only $x$. Therefore, $\mathcal{R}_{\mathcal{L}}$ takes as input only $x$ (witness is empty string whose length is $0$).

In other words, a string $x$ in a language $\mathcal{L} \in \mathsf{NP}$ has a short witness $w$ which can be used to verify in polynomial time that $x \in \mathcal{L}$, whereas $x$ in a language $\mathcal{L} \in \mathsf{P}$ has a polynomial time algorithm that checks $x \in \mathcal{L}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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