# Can one reduce a problem of unknown complexity to a hard problem to show hardness?

In this paper (page 3 Theorem 1) the authors want to prove that their problem is NP-complete. Their method is as follows. Let their problem be known as $P$. They show that their problem can be written as a $0\text{-}1$ integer program. Then they claim that $0\text{-}1$ integer programs are NP-complete and therefore their problem $P$ is NP-complete.

I find this proof hard to believe. For the problem $P$ to be NP-hard I think one has to reduce the $0\text{-}1$ integer program into an instance of problem $P$ and not the other way around.

Please can someone explain if this proof in the paper is acceptable?

• The proof shows, in a roundabout way, that the problem is in NP, not that the problem is NP hard. – Joe Jan 16 '14 at 20:37

You should not believe such a proof (still a claim might be true even if the proof is not). You can also see this by suddenly being able to "prove" silly things. The 2-SAT problem is a special case of the $k$-SAT problem, where each clause has exactly two literals. There are plenty of algorithms that solve 2-SAT in polynomial time, thus 2-SAT is in P. On the other hand, 3-SAT is already NP-complete.