I was going through the proof that DNF-SAT can be solved in polynomial time. The strategy was to go through all clauses, find a clause that doesn't contain both x and x' for any variable x and then output the satisfying assignment. The input size for this problem is the number of variables (say n). My doubt is that if you have no constraint on the number of literals in a clause, then you can have number of clauses exponential in n. How does the above algorithm work in case of exponential number of clauses? In many problems (like reduction from 3-SAT to Directed Hamiltonian cycle), the reduction or the algorithm takes time polynomial in number of clauses. So what guarantees that the number of clauses are polynomial in the size of the input?

  • 2
    $\begingroup$ It's polynomial in the input size $\endgroup$ Commented Oct 15, 2023 at 6:20


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.