Has anyone explored running times of 3-SAT or #2-SAT given by the occurrences of the highest occurring variable? In other words, if the variable that appears most often appears $x$ times, has anyone been able to give a runtime that is a function of $x$?

  • 2
    $\begingroup$ You can add a trivial set of clauses of linear size to make a new variable the one with the highest occurrence and it shouldn't have much effect on any reasonable SAT algorithm. $\endgroup$
    – Kaveh
    Nov 10, 2015 at 18:41
  • 3
    $\begingroup$ Not only that, but the problem remains NP-complete even if you bound the number of occurrences of each variable to be O(1). You can see this either by replacing frequent variables with new ones along with new clauses enforcing equality, or else just by observing that the Cook-Levin theorem only constructs CNFs with bounded variable frequency. $\endgroup$
    – Joe Bebel
    Nov 11, 2015 at 23:33


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.