Definition of NP Problem: Is it Yes or No?

[ak416]

(I asked this question also in Homework Help for Comp Sci and Engineering, but maybe someone in here can answer this)

Im just a little confused about the definition of an NP problem. The most common definition I hear is: a decision problem is in NP if it has a polynomial time certification. So if it is a yes or no question, there is a proof of it in polynomial time. But my question is, when proving a decision problem is in NP, do you have to assume the answer is yes and show a polytime certification exists and then assume the answer is no and show a polytime certification of that answer exists? Or do you choose either yes or no and show that a polytime certification of that answers exists?

 

[Hurkyl]

The thing required to be polynomial time is the algorithm that takes a certificate as input, and returns "valid" or "invalid".


(One thing to note -- if a problem is NP, then the certificate itself must occupy a polynomial amount of space! Otherwise, it couldn't be validated in polynomial time)

 

[ak416]

so for example if I want to prove that the problem: Does a graph G have a hamiltonian cycle? is NP, do I first assume there is a hamiltonian cycle and show that this can be certified in polynomial time, and then assume there isn't one, and show that this also can be certified in polynomial time?

 

[Hurkyl]

No; you assume someone has handed you a certificate that asserts the answer, and show that you can validate the certificate in polynomial time.


Here's a short proof that finding a factor of a number is NP:

I'm going to define a certificate as follows:

. A certificate consists of a single number X, written in binary.
. 0 < X < N.
. If X = 1, the certificate is asserting that N is prime.
. Otherwise, the certificate is asserting that X is a nontrivial factor of N.


Here's a validation scheme.

Input: An n-bit number number N, and an alledged certificate for N.

. Read up to n + 1 bits of the certificate to obtain a number X.
. If the end of the certificate has not been reached, output "invalid"
. If X = 0, output "invalid"
. if X = N, output "invalid"
. If X = 1, run the AKS primality test on N
... If N passes the AKS test, output "valid"
... If N fails the AKS test, output "invalid"
. If X > 1, perform the division algorithm on N / X
... If the remainder is zero, output "valid"
... If the remainder is nonzero, output "invalid"


I have defined a certificate for the solution to the problem:

. Find a nontrivial factor of N, if one exists.

I have presented an algorithm for validating such a certificate.

The validation algorithm runs in polynomial time, therefore the problem of determining a nontrivial factor of N if one exists is in NP.

 

[-Job-]

This is usually explained using an "Oracle". For example, suppose you have an Oracle who, when given a Graph of n nodes, and through some means, gives you back a Hamiltonian path for that graph.

Now you're interested in whether the Oracle made a mistake. So you verify that the path is a hamiltonian by checking the necessary conditions (i.e. that the path goes through every node exactly once). The process by which you verify the solution the Oracle gave you is the certificate.

If the process can be completed in polynomial time, then the problem is in NP.

So in order to determine whether the Hamiltonian Path problem is in NP you try to determine whether you can verify a solution to that problem in polynomial time.

In this case, it's easy. The oracle gives you a path. You check two things:
. That the path goes through every node.
. That the path goes through every node not more than once.

This can be done in O(n). Hence the Hamiltonian Path Problem has a certificate which runs in Polynomial time. So the HPP is in NP.

 

[CRGreathouse]

No; you assume someone has handed you a certificate that asserts the answer, and show that you can validate the certificate in polynomial time.

Yes, absolutely. Also (not to disagree but to elucidate) you must show:
* If a particular instance of the problem is false, no certificate is valid.
* If a particular instance of the problem is true, some certificate is valid.