Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-26T20:04:13.771Z Has data issue: false hasContentIssue false
  • English
  • Français

A model-theoretic proof for P ≠ NP over all infinite abelian group

Published online by Cambridge University Press:  12 March 2014

Mihai Prunescu
Mihai Prunescu*
Affiliation:
Institut für Mathematik und Informatik der Universität Greifswald, F.L.Jahn STR. 15A, 17489 Greifswald, Germany Institute of Mathematics of Romanian Academy, PO-Box 1-764, 70700 Bucharest, Romania, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 Gaßner.

Keywords

BSS-modelP ≠ NPabelian groupultraproduct
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 67 , Issue 1 , March 2002 , pp. 235 - 238
Copyright
Copyright © Association for Symbolic Logic 2002

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[A]Asser, Günter, Gaßner, Christine, and Prunescu, Mihai, Für alle unendlichen abelschen Gruppen G ist P(G) ≠ NP(G). (drei Beweise), preprint der Universität Greifswald, January 2000.Google Scholar
[BCSS]Blum, Lenore, Cucker, Felipe, Shub, Michael, and Smale, Steven, Complexity and real computation, Springer-Verlag, New-York, 1998.CrossRefGoogle Scholar
[BSS]Blum, Lenore, Shub, Michael, and Smale, Steven, On a theory of computation and complexity over the real numbers, American Mathematical Society Bulletin, vol. 21 (1989).CrossRefGoogle Scholar
[B]Bourgade, Menard, Separations et transferts dans la hierarchie polynomiale des groupes abeliens infinis, preprint, 2000.3.0.CO;2-S>CrossRefGoogle Scholar
[H]Hemmerling, Armin, On P vs. NP for parameter-free programs over algebraic structures, to appear in Mathematical Logic Quarterly.Google Scholar
[M]Meer, Klaus, Real number models under various sets of operations, Journal of Complexity, vol. 9, 1993.CrossRefGoogle Scholar
[P]Poizat, Bruno, Lespetits cailloux, Aleas, Lyon, 1995.Google Scholar