Problem Detail: 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 $0text{-}1$ integer program. Then they claim that $0text{-}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 $0text{-}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?
Asked By : Mat
Answered By : Juho
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/19541 Ask a Question Download Related Notes/Documents
