# Thread: proving something in NP

1. 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.

2.

3. Reducibility in one direction is basically used to show that the problem is NP, so that can usually be skipped if you have a good proof for it already. And NP means that it can be verified in polynomial time, not in NP time (which isn't actually a thing). If you need to use a solve an NP-complete problem to verify your solution, your problem probably isn't NP. (The usual thing is to make it so that solving some NP-complete problem provides a solution to your problem with minimal further work.)

The other thing is, being both NP and NP-hard isn't quite enough for NP-completeness (IIRC). The last thing is that if you could solve the new problem, you could solve all NP problems. This comes free with the proof by reduction. On the other hand, the chances of something being NP and NP-hard but not NP-complete seems slim and there may be some proof out there that no such thing exists (which would mean that proving something NP and NP-hard would automatically imply NP-completeness).

4. Thanks for the response, but I'm sorry to say that you do not recall correctly. With the possible exception of the original SAT proofs that defined the concepts of NP and NP-hardness, the primary way to prove that something is NP-complete is to prove that 1. it is contained in the set NP, and 2. that a known NP-complete problem is reducible to it, which proves that it is at least as hard as NP-complete problems (aka NP-hard).
just proving the 2nd could still mean that it is in a class that contains NP such as EXP.

As I mentioned, proving reducibility in both directions would prove that it's NP-complete, but I don't yet have a way to prove that my problem is reducibile to a known NP-complete problem, only the other way around.
here's a link to more basic information for you on proving NP-completeness:
stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete

5. I may be remembering the definition of NP-hard wrong, but NP-complete does mean that a solution to that problem would also be a solution to all other NP problems.

This was proven the hard way for the original SAT problem. All other NP-complete problems were then shown to reduce to SAT, which means that a solution to SAT would solve the other problem and vice versa. This is an important property (really, the defining property) of NP-complete problems.

Now, what I may be remembering wrong is whether or not the definition of NP-hard includes the "this could solve all NP problems" bit, but now that I think about it a bit, I'm pretty sure it does. It's a moot point anyway because you've already proven that part.

As for the first part, reducing your problem to an NP-complete problem is one way of proving it NP, but not the only way. To prove something is NP directly you need to demonstrate an algorithm that given a problem and a solution you can verify that that solution works for that problem in polynomial time.