An assertion concerning functionally complete algebras and NP-completeness

被引：8

作者：

Horvath, Gabor ^{[1
]}

Nehaniv, Chrystopher L. ^{[1
]}

Szabo, Csaba ^{[2
]}

机构：

[1] Univ Hertfordshire, Ctr Comp Sci & Informat Res, Hatfield AL10 9AB, Herts, England

[2] Eotvos Lorand Univ, Dept Algebra & Number Theory, H-1117 Budapest, Hungary

来源：

THEORETICAL COMPUTER SCIENCE | 2008年 / 407卷 / 1-3期

关键词：

Functionally complete algebras; Identity checking; Solvability of equations; Solvability of systems of equations; NP-completeness; coNP-completeness;

D O I：

10.1016/j.tcs.2008.08.028

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：591 / 595

页数：5

共 15 条

[1]

[Anonymous], THESIS MASARIK U BRN

[2] Results on the equivalence problem for finite groups [J].

Burris, S ;

Lawrence, J .

ALGEBRA UNIVERSALIS, 2005, 52 (04) :495-500

[3] THE EQUIVALENCE PROBLEM FOR FINITE RINGS [J].

BURRIS, S ;

LAWRENCE, J .

JOURNAL OF SYMBOLIC COMPUTATION, 1993, 15 (01) :67-71

[4]

Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[5] The complexity of solving equations over finite groups [J].

Goldmann, M ;

Russell, A .

FOURTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 1999, :80-86

[6] The complexity of the equivalence problem for nonsolvable groups [J].

Horvath, Gabor ;

Lawrence, John ;

Merai, Laszlo ;

Szabo, Csaba .

BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 2007, 39 :433-438

[7] The complexity of checking identities over finite groups [J].

Horvath, Gabor ;

Szabo, Csaba .

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2006, 16 (05) :931-939

[8] THE COMPLEXITY OF EQUIVALENCE FOR COMMUTATIVE RINGS [J].

HUNT, HB ;

STEARNS, RE .

JOURNAL OF SYMBOLIC COMPUTATION, 1990, 10 (05) :411-436

[9] Complexity of semigroup identity checking [J].

Kisielewicz, A .

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2004, 14 (04) :455-464

[10] Taylor terms, constraint satisfaction and the complexity of polynomial equations over finite algebras [J].

Larose, Benoit ;

Zadori, Laszlo .

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2006, 16 (03) :563-581

← 1 2 →