The Satisfiability Problem for Probabilistic Ordered Branching Programs.
Manindra AgrawalThomas ThieraufPublished in: Computational Complexity Conference (1998)
Keyphrases
- satisfiability problem
- np complete
- temporal logic
- search algorithm
- phase transition
- sat problem
- pspace complete
- stochastic local search algorithms
- stochastic local search
- max sat
- sat instances
- orders of magnitude
- model checking
- decision procedures
- mazurkiewicz traces
- weighted max sat
- modal logic
- constraint satisfaction problems
- knowledge representation