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.
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 ...
Carvalho, Catarina (2009-08)
Erratum to: The complete nucleotide sequence of a totivirus from Aspergillus foetidus (Arch Virol, 10.1007/s00705-012-1368-x) Kozlakidis, Z.; Herrero, N.; Coutts, Robert H.A. (2013-02)