Knuth-Bendix constraint solving is NP-complete
  We show the NP-completeness of the existential theory of term algebras with the Knuth-Bendix order by giving a nondeterministic polynomial-time algorithm for solving Knuth-Bendix ordering constraints. 
Konstantin Korovin and Andrei Voronkov