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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,031

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

A Model-theoretic Proof For {$\roman P\neq {\rm Np}$} Over All Infinite Abelian Groups.Mihai Prunescu - 2002 - Journal of Symbolic Logic 67 (1):235-238.
P_≠ _NP for all infinite Boolean algebras.Mihai Prunescu - 2003 - Mathematical Logic Quarterly 49 (2):210-213.
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.

Analytics

Added to PP
2009-01-28

Downloads
427 (#48,592)

6 months
11 (#271,985)

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.
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-5):507-519.

Add more references