P ≠ NP for all infinite Boolean algebras

DOI10.1002/MALQ.200310020MaRDI QIDQ4804182zbMATH OpenOpenAlexFDO

Authors Mihai Prunescu

Publication date 10 April 2003

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.200310020

zbMATH Keywords

computability over algebraic structuresinfinite Boolean ringsP-NP-problem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Ring-theoretic properties of Boolean algebras (06E20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• P NP for infinite time Turing machines
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• scientific article; zbMATH DE number 2163541
• Pf ≠ NPf for almost all f
• scientific article; zbMATH DE number 953010
• scientific article; zbMATH DE number 1421070
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• The Nonapproximability of Non-Boolean Predicates
• scientific article; zbMATH DE number 1833417
• \(\mathrm P \overset {?} {=} \mathrm{NP}\)

Cited in

(5)

• On the P-NP problem over real matrix rings
• Two situations with unit-cost: ordered abelian semi-groups and some commutative rings
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• A model-theoretic proof for P ≠ NP over all infinite abelian group
• The path-bifurcation hierarchy does not collapse to ^1 in infinite abelian groups

This page was built for publication: P ≠ NP for all infinite Boolean algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4804182)