On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction
Peter JonssonPaolo LiberatorePublished in: Electron. Colloquium Comput. Complex. (1999)
Keyphrases
- constraint satisfaction
- phase transition
- constraint satisfaction problems
- heuristic search
- constraint propagation
- sat problem
- combinatorial problems
- relaxation labeling
- constraint programming
- max sat
- satisfiability problem
- constraint relaxation
- soft constraints
- sat solvers
- product configuration
- space complexity
- probabilistic reasoning
- search algorithm
- arc consistency
- worst case
- computational complexity
- np complete
- constraint optimization
- robust fault detection
- constraint networks
- decision problems
- expert systems
- constraint solving
- constrained problems
- random instances
- genetic algorithm
- russian doll search