Knuth-Bendix constraint solving is NP-complete
classification
💻 cs.LO
keywords
knuth-bendixsolvingalgebrasalgorithmconstraintconstraintsexistentialgiving
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.