Algebraic Structures with Hard Equivalence and Minimization Problems
Peter A. Bloniarz, Harry B. Hunt, Daniel J. Rosenkrantz · Journal of the ACM · 1984
The relationship between the setting in which an algebraic problem is posed and the complexity of solving the problem is considered.The problems stud~ed are equivalence, minimization, and approximate mimmlzatlon problems for formulas revolving variables, parentheses, operators, and (optionally) constants.General suffioent condmons on an algebraic structure Y for these problems to be NP-or coNP-hard are presented.Apphcations are gwen to a number of specific algebraic structures of independent interest including lattices, semirings, regular algebras, finite fields, rings 7/k, and Boolean nngs.Apphcations are also gwen to systems of rewrite rules and to several simple programming languages.