The Satisfiability Problem for Probabilistic Ordered Branching Programs
Manindra AgrawalThomas ThieraufPublished in: Electron. Colloquium Comput. Complex. (1997)
Keyphrases
- satisfiability problem
- np complete
- temporal logic
- phase transition
- search algorithm
- stochastic local search algorithms
- sat problem
- decision procedures
- max sat
- mazurkiewicz traces
- pspace complete
- orders of magnitude
- model checking
- sat instances
- special case
- computational complexity
- randomly generated
- constraint satisfaction problems