Complexity of the Satisfiability Problem for a Class of Propositional Schemata.
Vincent AravantinosRicardo CaferraNicolas PeltierPublished in: LATA (2010)
Keyphrases
- satisfiability problem
- pspace complete
- np complete
- temporal logic
- search algorithm
- conjunctive normal form
- sat problem
- phase transition
- cnf formula
- first order logic
- sat instances
- computational complexity
- stochastic local search algorithms
- decision procedures
- max sat
- stochastic local search
- randomly generated
- propositional logic
- clause learning
- propositional formulas
- mazurkiewicz traces
- causal graph
- boolean formula
- finite domain
- decision problems
- constraint satisfaction