The complexity of equivalence for commutative rings

DOI10.1016/S0747-7171(08)80053-3zbMath0724.68050MaRDI QIDQ758209

Richard E. Stearns, Harry B. III Hunt

Publication date: 1990

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

straight-line programscommutative ringsequivalence problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects and applications of commutative rings (13P99) Finite commutative rings (13M99)

Related Items

Complexity of the identity checking problem for finite semigroups., Computers and universal algebra: Some directions, COMPLEXITY OF SEMIGROUP IDENTITY CHECKING, Complexity issues of checking identities in finite monoids, Satisfiability in MultiValued Circuits, Some applications of higher commutators in Mal'cev algebras, Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\)., Identity checking problem for transformation monoids, The complexity of the equivalence and equation solvability problems over nilpotent rings and groups., The complexity of the equation solvability problem over semipattern groups, THE EQUIVALENCE PROBLEM OVER FINITE RINGS, An assertion concerning functionally complete algebras and NP-completeness, COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES, THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM, Evaluation of polynomials over finite rings via additive combinatorics, THE COMPLEXITY OF THE EQUIVALENCE PROBLEM OVER FINITE RINGS, THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS, The complexity of the equivalence and equation solvability problems over meta-abelian groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the computational power of pushdown automata
• The Complexity of Very Simple Boolean Formulas with Applications
• Algebraic Structures with Hard Equivalence and Minimization Problems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• Nonlinear Algebra and Optimization on Rings are “Hard”
• The complexity of theorem-proving procedures