Given a Boolean expression, you can always determine whether is satisfiable or n

Question

Given a Boolean expression, you can always determine whether is satisfiable or not by constructing a truth table. Is there a more efficient algorithm? Surprisingly, this is considered one of the most important unsolved problems in mathematics, and a solution is currently worth $1,000,000. In this project, you will implement a clever algorithm for solving 3-SAT. Your input will be a Boolean expression in either conjunctive normal form or disjunctive normal form (your choice). You will then give a truth assignment that makes the expression true or state that such an assignment is impossible. Take a look at this article for some ideas.

Explanation / Answer

we can convert a boolean formula into DNF, but the resulting formula will be very much larger than the original formula—in fact, and so exponentially. Since the conversion algorithm must at the very least write out the resulting DNF formula, its running time will be at least the length of the output, and hence its worst-case running time will be exponential.

Even if we somehow finish the issue of writing out the DNF version of the input formula, the algorithm we propose will take a formula of size x, converts it into a DNF formula of worst-case size 2^x, and then it calculates the satisfiability
of DNF formula in time Z(2^x) for some polynomial Z.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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