Knuth-Bendix Constraint Solving Is NP-Complete.

Konstantin Korovin, Andrei Voronkov

Browse the full ICALP paper archive.