proving something in NP

[RSW2111]

Hi,

 

I have a new graph problem which, due to it's 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.

[imatfaal]

If you can reduce it to a known np problem in polynomial time (ie np-hard), and verify a solution in polynomial time (ie np) then I think you are set to say that it is np-complete. You need to have both (not either as I think you might be suggesting) for it to be np-complete

http://mathworld.wolfram.com/NP-Problem.html

 

The verification of a solution is in polynomial time contra yours above

[RSW2111]

Thanks for your response, but I think you misunderstood what I wrote. I don't yet have a way of proving that my problem is reducible to a known NP-complete problem. I have a way of proving that a known NP-complete problem is reducible to it.

If I had the first, that would prove that it is in NP.

The second proves that, if it is in NP, it is at least as hard as a known NP-complete problem. This is what's referred to as NP-hardness.

Since I don't yet have the first, I am looking for a logical proof that it is in NP instead of a reduction. Logical proofs are often used for this, but in general the proofs show that the verification can be done using a polynomial time algorithm. My logical proof shows that the verification can be done using a non-deterministic polynomial time algorithm. I am trying to figure out if that is sufficient.

Sorry if that all was unclear before.