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.
Complete Communities or Dormitory Towns? Case Studies in Interwar Housing at Welwyn Garden City, Becontree and St Helier Benjamin, Matthew (2016-11-23)Housing has always been a paramount issue; in the late nineteenth and early twentieth century attempts were made to revolutionise the problem of poor quality houses and the accompanying poor quality of life. This was set ...
Herbert, Peter David (2013-04-10)In this thesis I investigate the hosts and cluster environments of a sample of 41 radio galaxies between z = 0.4 and z = 0.6. I use spectroscopic data for a 24 object subsample to investigate their star formation histories ...
Use of the repertory grid as a nomothetic measure in psychotherapy research : an example of optimal functioning, or of failure to complete the experience cycle? Watson, Sue; Winter, David (EPCA, 1999)