Approximating the satisfiability threshold for random k-XOR-formulas
Nadia CreignouHervé DaudéOlivier DuboisPublished in: CoRR (2001)
Keyphrases
- random sat
- cnf formula
- phase transition
- satisfiability problem
- random constraint satisfaction problems
- conjunctive normal form
- propositional formulas
- propositional logic
- computational complexity
- random instances
- roc curve
- randomly generated
- boolean formula
- sat problem
- decision procedures
- np complete
- threshold selection
- exact computation
- thresholding algorithm
- data sets