Two situations with unit-cost: ordered abelian semi-groups and some commutative rings

DOI10.1016/j.jco.2004.09.005zbMath1096.03054MaRDI QIDQ2387423

Mihai Prunescu

Publication date: 2 September 2005

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2004.09.005

zbMATH Keywords

polynomial hierarchy; arithmetical hierarchy; complexity classes; products of rings; algebraic knapsack problem; ordered abelian semigroups; unit-cost complexity

Mathematics Subject Classification ID

03C60: Model-theoretic algebra

03D15: Complexity of computation (including implicit computational complexity)

06F05: Ordered semigroups and monoids

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03D10: Turing machines and related notions

03D75: Abstract and axiomatic computability and recursion theory