Abstract
For several different algebraic structures S, we study the computational complexity of such problems as determining, for a system of equations on S,
-
1.
if the system has a solution,
-
2.
if the system has a unique solution, and
-
3.
the number of solutions of the system.
Three types of results are obtained. For rings S, we show that these problems are either NP- or coNP-hard, when S is unitary, and in addition, are SAT-hard(npoylogn,n), when S is commutative and unitary. We also show that determining the number of solutions of a system of equations on S is #P-complete, when S is finite and unitary, and in addition, is #SAT-complete(npolylogn,n), when S is finite, commutative, and unitary. Second for all ordered unitary rings S, we show that determining if a system of equations on S has a unique solution is intuitively “as hard as” determining if a system of equations on S has a solution. Third, we characterize the complexity of these problems for additional algebraic structures including each finite or finite-depth lattice.
This research was supported in part by NSF Grant No. DCR 86-03184.
This research was supported in part by NSF Grant No. DCR 83-03932.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974.
R.C. Backhouse and B.A. Carre, “Regular algebra applied to path finding problems,” J. Inst. Maths. Applics., vol. 15, pp. 161–186, 1975.
G. Birkhoff, Lattice Theory (3rd Edition), Am. Math. Soc., Providence, R.I., 1967.
J.H. Conway, Regular Algebra and Finite Machines, Chapman and Hill, Ltd., London, 1971.
S.A. Cook, “The complexity of theorem-proving procedures,” Proc. Third Annual ACM Symp. on Theory of Computing, pp. 151–158, 1971.
M. Davis, Computability and Unsolvability, Dover Publications, Inc., New York, 1982.
S. Eilenberg, Automata, Languages, and Machines, vol. A, Academic Press, New York, 1974.
A.S. Fraenkel and Y. Yesha, “Complexity of problems in games, graphs, and algebraic equations,” unpublished manuscript, 1977.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, Ca., 1979.
H.B. Hunt III and R.E. Stearns, “Nonlinear algebra and optimization on rings are “hard”,” SICOMP, vol. 16, pp. 910–929, 1987.
H.B. Hunt III and R.E. Stearns, “The complexities of satisfiability problems for algebraic structures,” in preparation, 1988.
H.B. Hunt III and R.E. Stearns, “On the complexities of equivalence for communtative rings,” Technical Report 87-22, SUNY Albany, 1987 (submutted for publication). Also see Abstracts of Communications at 5-th International Conference on: Applied Algebra, Error-Correcting Codes and Cryptography, Applied Algorithms and Combinatorics, Computer Algebra and Complexity Theory, pp. 43–44, Menorca, Spain.
H.B. Hunt III, R.E. Stearns, and S.S. Ravi, “SAT, Finite Algebra, and the structure of NP,” in preparation, 1988.
R.M. Karp, “Reducibility among combinational problems,” in Complexity of Computer Computations, ed. R.E. Miller and J.W. Thatcher, pp. 85–103, Plenum Press, New York, 1972.
R.L. Lipton and R.E. Tarjan, “Applications of a planar separator theorem,” SICOMP, vol. 9, pp. 615–627, 1980.
S. MacLane and G. Birkhoff, Algebra, MacMillan, New York, 1967.
Yu.V. Matisjasevic, “Enumerable sets are diophantine,” Soviet Math. Dokl., vol. 77, pp. 354–357, 1970. (English translation).
S.S. Ravi and H.B. Hunt III, “Application of planar separator theorem to counting problems,” IPL, vol. 25, pp. 317–321, 1987.
R.E. Stearns and H.B. Hunt III, “On the complexity of the satisfiability problem and the structure of NP,” Technical Report 86-21, Department of Computer Science, SUNY at Albany, Albany, New York, 1986.
R.E. Tarjan, “A unified approach to path problems,” J. ACM, vol. 28, pp. 577–593, 1980.
L.G. Valiant, “The complexity of enumeration and reliability problems,” SICOMP, vol. 8, pp. 410–421, 1979.
B.L. van der Waerden, Modern Algebra volumes 1 and 2, Frederick Ungar Publishing Co., New York, 1953.
U. Zimmermann, Linear and Combinatorial Optimization in Ordered Algebraic Structures, North Holland, Amsterdam, 1981.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hunt, H.B., Stearns, R.E. (1989). On the complexity of satisfiability problems for algebraic structures (preliminary report). In: Mora, T. (eds) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 1988. Lecture Notes in Computer Science, vol 357. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51083-4_64
Download citation
DOI: https://doi.org/10.1007/3-540-51083-4_64
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51083-3
Online ISBN: 978-3-540-46152-4
eBook Packages: Springer Book Archive