Knuth-Bendix Constraint Solving Is NP-Complete.
Konstantin KorovinAndrei VoronkovPublished in: ICALP (2001)
Keyphrases
- constraint solving
- np complete
- knuth bendix
- constraint satisfaction problems
- constraint satisfaction
- term rewriting
- constraint propagation
- constraint programming
- constraint logic programming
- np hard
- rewrite systems
- constraint solver
- satisfiability problem
- function symbols
- randomly generated
- computational complexity
- arc consistency
- theorem proving
- combinatorial problems
- operational semantics
- databases
- tree search
- special case
- relational databases
- knowledge base