Skip to main content
added 19 characters in body
Source Link
Steven
  • 29.8k
  • 2
  • 29
  • 49

Are we talking about solutions or certificates? Since NP-complete problems are decision problems, a solution (to each instance) is always either "yes" or "no" and hence it's unique.

If we are talking about certificates, then no. Each yes-instance of a NP-complete problem admits infinitely many polynomial-length certificates. Indeed if $c$ is a yes-certificate and $T$ is a verifier, then you can always consider the certificate obtained by prepending, e.g., any number $k$ of zeros to $c$. The corresponding verifier is obtained from $T$ by first dropping the leading $k$ zeroes and then simulating $T$.

Are we talking about solutions or certificates? Since NP-complete problems are decision problems, a solution is always either "yes" or "no" and hence it's unique.

If we are talking about certificates, then no. Each NP-complete problem admits infinitely many polynomial-length certificates. Indeed if $c$ is a yes-certificate and $T$ is a verifier, then you can always consider the certificate obtained by prepending, e.g., any number $k$ of zeros to $c$. The corresponding verifier is obtained from $T$ by first dropping the leading $k$ zeroes and then simulating $T$.

Are we talking about solutions or certificates? Since NP-complete problems are decision problems, a solution (to each instance) is always either "yes" or "no" and hence it's unique.

If we are talking about certificates, then no. Each yes-instance of a NP-complete problem admits infinitely many polynomial-length certificates. Indeed if $c$ is a yes-certificate and $T$ is a verifier, then you can always consider the certificate obtained by prepending, e.g., any number $k$ of zeros to $c$. The corresponding verifier is obtained from $T$ by first dropping the leading $k$ zeroes and then simulating $T$.

Source Link
Steven
  • 29.8k
  • 2
  • 29
  • 49

Are we talking about solutions or certificates? Since NP-complete problems are decision problems, a solution is always either "yes" or "no" and hence it's unique.

If we are talking about certificates, then no. Each NP-complete problem admits infinitely many polynomial-length certificates. Indeed if $c$ is a yes-certificate and $T$ is a verifier, then you can always consider the certificate obtained by prepending, e.g., any number $k$ of zeros to $c$. The corresponding verifier is obtained from $T$ by first dropping the leading $k$ zeroes and then simulating $T$.