NP Completeness of 3-SAT problem [closed]
-
31-10-2019 - |
سؤال
I have started reading on algorithmic complexity for my thesis work. Already have studied on Polynomial time reducibility, NP-Complete, NP-Hard. Now trying to prove NP completeness of some of the classical problems. I have started with 3-SAT problem.
3-SAT problem — was shown to be NP-complete:
Input: A boolean Formula F in CNF where each clause contains at most three variables.
Question: Is that formula satisfiable?
Show now that the simple 3-SAT problem is also NP-complete:
Input: A boolean Formula F in CNF where each clause contains at most three variables and only clauses of length two may contain negated variables.
Question: Is that formula satisfiable?
Can any please explain the main idea? Thank you in advance.
لا يوجد حل صحيح