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 '15 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 '15 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.