On the complexity of trial and error for constraint satisfaction problems.
Gábor IvanyosRaghav KulkarniYouming QiaoMiklos SanthaAarthi SundaramPublished in: J. Comput. Syst. Sci. (2018)
Keyphrases
- constraint satisfaction problems
- constraint satisfaction
- constraint propagation
- constraint programming
- search space
- np complete
- arc consistency
- non binary
- combinatorial problems
- decomposition methods
- constraint solving
- constraint problems
- computational problems
- soft constraints
- space complexity
- partial constraint satisfaction
- np hard
- computational complexity
- backtracking search
- forward checking
- finite domain
- sat problem
- product configuration
- constraint networks
- worst case
- constraint optimization
- pseudo boolean optimization
- constraint solver
- optimal solution
- backtracking algorithm
- arc consistency algorithm