Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.tcs.2008.08.028 | Theoretical Computer Science |
Keywords | DocType | Volume |
Functionally complete algebras,Identity checking,Solvability of equations,Solvability of systems of equations,NP-completeness,coNP-completeness | Journal | 407 |
Issue | ISSN | Citations |
1 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gábor Horváth | 1 | 210 | 35.47 |
| Chrystopher L. Nehaniv | 2 | 1219 | 138.00 |
| Csaba A. Szabo | 3 | 48 | 7.08 |