An assertion concerning functionally complete algebras and NP-completeness
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.
Published inTheoretical Computer Science
RelationsSchool of Computer Science
MetadataShow full item record
Showing items related by title, author, creator and subject.
Lebcir, Mohamed; Choudrie, Jyoti (2011-12-01)The aim of this paper if to investigate the factors driving project complexity in construction projects and how they impact on project cycle time. This issue has been addressed by building a framework for project complexity ...
Davies, K. (2006)This article considers the findings of a small-scale study of the practice of case managers supervising offenders required to attend the Think First Group. It explores the interface between one-to-one and group-based work ...
A complete 8-GHz QPSK-MODEM featuring novel subcarrier and data synchronization for optical communications Kourtessis, P.; Walker, S.D. (2007)