In this paper (page 3 Theorem 1) the authors want to prove that their problem is

Question

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-1 integer program. Then they claim that 0-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-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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.