5
$\begingroup$

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?

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

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.

Consider the following "theorem" and "proof".

"Theorem:" 2-SAT is NP-complete. "Proof:" Given an instance of 2-SAT, duplicate a literal in every clause to produce an instance of 3-SAT. Because 3-SAT is NP-complete, we conclude that so is 2-SAT.

We of course know this is nonsense.

$\endgroup$
  • $\begingroup$ That paper is being cited by many others. So I didn't want to assume it was incorrect just by my instinct. I hope IEEE will correct this. $\endgroup$ – Mat Jan 7 '14 at 13:59
  • 2
    $\begingroup$ @triomphe If you think you've discovered an error in a paper, you might want to check out this question on Academia.SE. $\endgroup$ – Juho Jan 7 '14 at 14:12
6
$\begingroup$

The proof is not correct. As you've indicated the reduction needs to go in the other direction, i.e. integer programming must be reduced to their problem, not the other way around.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.