MAJORITY-3SAT (and Related Problems) in Polynomial Time.
Shyan AkmalRyan WilliamsPublished in: FOCS (2021)
Keyphrases
- related problems
- sat solvers
- special case
- broadly applicable
- satisfiability problem
- sat problem
- approximation algorithms
- phase transition
- propositional satisfiability
- stable marriage
- search algorithm
- sat solving
- range searching
- boolean satisfiability
- sat instances
- max sat
- computational complexity
- boolean formula
- search strategies
- np complete