  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.
