Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm a computer science student and I'm having some problem understanding the verifier based definition of NP problems.

The definition says that a problem is in NP if can be verified in polynomial time by a deterministic Turing machine, given a "certificate".

But what happens, if the certificate is exactly the problem solution? It's only a bit, and it's obviously polynomially limited by the input size, and it's obviously verifiable in constant, thus polynomial time.

In other words, i define the certificate as the output of the problem for a given input and the verifier will only verify that its input will be a bit of value 1.

Therefore, each decision problem would belong to NP.

share|improve this question

migrated from cstheory.stackexchange.com Jul 4 '11 at 23:55

This question came from our site for theoretical computer scientists and researchers in related fields.

2  
Your definition is like a Turing machine that says yes to everything -- does that render every problem decidable? –  Rahul Jul 5 '11 at 0:06
add comment

2 Answers 2

The requirement for NP is that we want the algorithm to have the property that a problem instance is affirmative if and only if there is a certificate such that the algorithm accepts the problem instance with that certificate. That is, a set $A$ is in NP when there is an algorithm $p$ such that $x\in A$ if and only if there is $y$ such that $p$ accepts $(x,y)$, and $p$ runs on every $(x,y)$ in polynomial time of $|x|$.

If I understand you, you are proposing that the certificate $y$ should simply be an indicator for whether $x\in A$ or not. That is, your algorithm would seem to accept all input of the form $(x,{\it \text{yes}})$, and reject otherwise. With this algorithm, you will indeed have the property that $x\in A$ implies there is $y$ such that $p$ accepts $(x,y)$, since we can let $y$ be yes. But you will not achieve the reverse implication, since your algorithm will accept $(x,y)$ whenever $y$ says yes, and so it has the capacity to be fooled, accepting $(x,{\it\text{yes}})$ even when $x\notin A$, when we do not want it to be accepted.

The point of NP is that problems are in NP when they can be set up in the certificate style, so that an acceptable certificate exists only for the inputs that are truly in the set. So, in the case of the 3-sat problem, for example, a Boolean expression has a satisfying instance if and only if there is an assignment of the Boolean variables making the expression true. So the certificate will be the variable assignment, and it can be checked whether such a certificate is correct in polynomial time.

Perhaps it will help you to observe that $x\in A$ does not necessarily imply that $p$ accepts every $(x,y)$, only that there is a $y$ which $p$ accepts. In particular, just because $p$ rejects a particular $(x,y)$, it doesn't mean that we may conclude that $x\notin A$; instead, it just means that we haven't yet verified $x\in A$, and perhaps it may be impossible to verify this, but we can't be sure yet.

share|improve this answer
add comment

Clearly, not every solution to a problem could work as a certificate. This is easy to see with an example. Take the following example:

TAUTOLOGY = $\{\varphi \mid \forall u \in \{0,1\}^n: \varphi(u) = 1\}$

This problem is a coNP-complete problem. An answer from an algorithm for this problem would just be yes or no. Providing yes or no as a certificate does not help us, hence we still have to exhaustively search whether the formula is a tautology or not. This because we simply do not know whether this problem has short certificates which allow polynomial time computations (assuming the conjecture that NP $\neq$ coNP).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.