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

DOI10.1016/j.jco.2004.09.005zbMath1096.03054OpenAlexW1977485022MaRDI 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 hierarchyarithmetical hierarchycomplexity classesproducts of ringsalgebraic knapsack problemordered abelian semigroupsunit-cost complexity

Mathematics Subject Classification ID

Model-theoretic algebra (03C60) Complexity of computation (including implicit computational complexity) (03D15) Ordered semigroups and monoids (06F05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10) Abstract and axiomatic computability and recursion theory (03D75)

Cites Work

• A survey on real structural complexity theory
• Real number models under various sets of operations
• P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)
• On P Versus NP for Parameter-Free Programs Over Algebraic Structures
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• Accessible telephone directories
• A model-theoretic proof for P ≠ NP over all infinite abelian group
• P ≠ NP for all infinite Boolean algebras
• The P-DNP problem for infinite Abelian groups
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Two situations with unit-cost: ordered abelian semi-groups and some commutative rings