A model-theoretic proof for P ≠ NP over all infinite Abelian groups

Journal of Symbolic Logic 67 (1):235 - 238 (2002)
  Copy   BIBTEX

Abstract

We give a model-theoretic proof of the fact that for all infinite Abelian groups P ≠ NP in the sense of binary nondeterminism. This result has been announced 1994 by Christine Gabner

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1190150041

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,130

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

P ≠ NP for all infinite Boolean algebras.Mihai Prunescu - 2003 - Mathematical Logic Quarterly 49 (2):210-213.
Separations et transferts dans la hierarchie polynomiale des groupes abeliens lifinis.Ménard Bourgade - 2001 - Mathematical Logic Quarterly 47 (4):493-502.
The additive group of the rationals does not have an automatic presentation.Todor Tsankov - 2011 - Journal of Symbolic Logic 76 (4):1341-1351.
A game‐theoretic proof of analytic Ramsey theorem.Kazuyuki Tanaka - 1992 - Mathematical Logic Quarterly 38 (1):301-304.
Abelian‐by‐G Groups, for G Finite, from the Model Theoretic Point of View.Annalisa Marcja & Carlo Toffalori - 1994 - Mathematical Logic Quarterly 40 (1):125-131.
On superstable CSA-groups.Abderezak Houcine - 2008 - Annals of Pure and Applied Logic 154 (1):1-7.
On superstable CSA-groups.Abderezak Ould Houcine - 2008 - Annals of Pure and Applied Logic 154 (1):1-7.
Elimination of unbounded quantifiers for some poly-regular groups of infinite rank.Philip Scowcroft - 2007 - Annals of Pure and Applied Logic 149 (1-3):40-80.
The dp-rank of Abelian groups.Yatir Halevi & Daniel Palacín - 2019 - Journal of Symbolic Logic 84 (3):957-986.
Space complexity of Abelian groups.Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin - 2009 - Archive for Mathematical Logic 48 (1):115-140.

Analytics

Added to PP
2009-01-28

Downloads
445 (#64,009)

6 months
8 (#574,086)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

P ≠ NP for all infinite Boolean algebras.Mihai Prunescu - 2003 - Mathematical Logic Quarterly 49 (2):210-213.

Add more citations

References found in this work

Characterizations of the class Δ ta 2 over Euclidean spaces.Armin Hemmerling - 2004 - Mathematical Logic Quarterly 50 (4):507-519.

Add more references