Suppose i have a CNF formula. If i negate the CNF formula, then i obtain DNF formula. However, i can't find anywhere on internet that mention the time complexity. What is the time complexity of negating a CNF formula and converting it to DNF formula?

  • $\begingroup$ It takes linear time. $\endgroup$ Jun 6, 2022 at 17:44
  • $\begingroup$ @YuvalFilmus yes it takes linear time, but i need to cite a paper that proved it takes linear time. $\endgroup$
    – LLL
    Jun 6, 2022 at 18:30
  • $\begingroup$ Can you provide an example? Negating a formula on CNF form does not produce a formula on DNF form. $\endgroup$ Jun 6, 2022 at 19:11
  • $\begingroup$ There is no reason to expect this particular claim to appear anywhere. Do you need a citation for 12+34=46? $\endgroup$ Jun 6, 2022 at 22:58
  • 2
    $\begingroup$ It depends on your audience. It would be perfectly appropriate in a computer science paper. $\endgroup$ Jun 7, 2022 at 5:55


Your Answer

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