proving something in NP

[RSW2111]

Hi,

I have a new graph problem which, due to its similarities to other known problems, I'm fairly certain that it is contained in NP and is NP-hard (the 2 necessary ingredients for NP-completeness). I have a proof that it is NP-hard, however, proving that it's contained in NP is turning out to be difficult.

My understanding of the normal process for doing this is to prove either reducibility from both directions or to prove that, given a potential solution, the solution can be verified in polynomial time.

I have a potential solution and a proof that the solution can be verified in NP time (using a known NP-complete problem). My question is: Is that sufficient to prove that my problem is in NP?

My gut says no, but various burritos have remarked to me that my gut is not always correct.

Thanks in advance for any help.

 

[esun]

No, the solution has to be verifiable in polynomial time. I wrote a long post about P vs NP awhile ago, I'll just link it here:

http://forums.anandtech.com/showpost.php?p=30874851&postcount=5

 

[RSW2111]

follow up question:
assuming P != NP, is the fact that the verification takes NP time sufficient to prove that the problem is not in NP?

I would guess that this would depend on whether or not that's a definite lower bound on the verification

 

[esun]

If you can prove that it cannot be verified in polynomial time then that would show the problem is not in NP. This is regardless of whether P=NP.

Remember that P is the set of decision problems that can be solved in polynomial time while NP is the set of problems whose solutions can be verified in polynomial tine. These definitions are not affected by whether P=NP.

 

[RSW2111]

I don't follow. If P=NP, then the set of decision problems that can be solved in polynomial time is the same as the set of problems that can be verified in polynomial time.

 

[esun]

My point is, if you prove that verification cannot be done in polynomial time, then the problem is not in NP. It doesn't matter if P=NP (your "Assuming P != NP" statement isn't required).