Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity.
Sangxia HuangPublished in: Electron. Colloquium Comput. Complex. (2012)
Keyphrases
- randomly generated
- sat instances
- random instances
- phase transition
- error bounds
- satisfiability problem
- error correction
- approximation algorithms
- np complete
- closed form
- approximation methods
- sat solvers
- stochastic local search
- approximation error
- relative error
- training instances
- max sat
- genetic algorithm
- branch and bound algorithm
- np hard
- decision trees