The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis.
Tomoyuki YamakamiPublished in: MFCS (2017)
Keyphrases
- satisfiability problem
- conjunctive normal form
- linear space
- boolean formula
- np complete
- sat problem
- search algorithm
- sat instances
- phase transition
- temporal logic
- stochastic local search
- external memory
- max sat
- boolean satisfiability
- dynamic programming
- special case
- genetic algorithm
- model checking
- upper bound
- sat solvers
- propositional logic
- np hard
- polynomial size