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.