| CPSC 327 | Data Structures and Algorithms | Spring 2024 |
To show that a problem is in NP requires two things: that it is polynomial-time verifiable (you can check that a "yes" solution is correct in polynomial time) and that the problem is a decision problem. Don't forget the decision problem part!
Be careful with the direction of the reduction: to show that a problem is NP complete, you need to reduce a known NP complete problem to it:
known NP ------> your ------> known NP
complete problem complete
That means turning an instance of the known problem's input into an instance of your problem's input, and then turning your problem's output into the solution for the known problem. Both parts need to be specified, though for decision problems the latter is often trivial.
To specify a reduction for an NP-completeness proof, you don't need to address how to solve your problem — this isn't an algorithm design task, but rather an argument about the (non-)existence of an efficient algorithm.