University of Hertfordshire

From the same journal

By the same authors

An assertion concerning functionally complete algebras and NP-completeness

Research output: Contribution to journalArticle

View graph of relations
Original languageEnglish
Pages (from-to)591-595
JournalTheoretical Computer Science
Publication statusPublished - 2008


In a paper published in J. ACM in 1990, Tobias Nipkow asserted that the problem of deciding whether or not an equation over a nontrivial functionally complete algebra has a solution is NP-complete. However, close examination of the reduction used shows that only a weaker theorem follows from his proof, namely that deciding whether or not a system of equations has a solution is NP-complete over such an algebra. Nevertheless, the statement of Nipkow is true as shown here. As a corollary of the proof we obtain that it is coNP-complete to decide whether or not an equation is an identity over a nontrivial functionally complete algebra.


Original article can be found at : Copyright Elsevier [Full text of this article is not available in the UHRA]

ID: 87441