<p>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$?</p>

CC BY-SA 3.0
2015-11-10T18:41:43.300Z
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.
Kaveh
CC BY-SA 3.0
2015-11-11T23:33:19.710Z
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.
Joe Bebel
<sat>
#2-SAT or 3-SAT and variable that appears most often
Matt Groff
# #2-SAT or 3-SAT and variable that appears most often

(Asked by: username_0 on 2015-11-10)

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$?

**Tags:** sat
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  

---

## 0 answers

