Knuth-Bendix constraint solving is NP-complete.
Konstantin KorovinAndrei VoronkovPublished in: ACM Trans. Comput. Log. (2005)
Keyphrases
- constraint solving
- np complete
- knuth bendix
- constraint satisfaction problems
- term rewriting
- constraint satisfaction
- constraint logic programming
- constraint propagation
- np hard
- rewrite systems
- constraint programming
- randomly generated
- constraint solver
- computational complexity
- function symbols
- satisfiability problem
- arc consistency
- combinatorial problems
- theorem prover
- constraint networks
- special case
- theorem proving
- temporal constraints
- sat solvers
- phase transition
- bounded treewidth
- branch and bound algorithm
- object oriented
- knowledge base