Professor jagger proposes to show that


Professor Jagger proposes to show that SAT<=p 3-CNF-SAT by using only the truth-table technique in the proof of theorem 34.10(Satisfiability of boolean formulas in 3-conjunctive normal form is NP-complete), and not other steps. That is, the professor proposes to take the boolean formula phi, form a truth table for its variables, derive from the truth table a formula in 3-DNF that is equivalent to -phi, and then negate and apply DeMorgan's laws to produce a 3-CNF formula equivalent to phi. Show that this strategy does not yield a polynomial-time reduction.

Request for Solution File

Ask an Expert for Answer!!
Basic Computer Science: Professor jagger proposes to show that
Reference No:- TGS0142590

Expected delivery within 24 Hours