Accessible Telephone Directories
Goode, John B.
J. Symbolic Logic, Tome 59 (1994) no. 1, p. 92-105 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We reduce to a standard circuit-size complexity problem a relativisation of the $P = NP$ question that we believe to be connected with the same question in the model for computation over the reals defined by L. Blum, M. Shub, and S. Smale. On this occasion, we set the foundations of a general theory for computation over an arbitrary structure, extending what these three authors did in the case of rings.
Publié le : 1994-03-14
Classification:  
@article{1183744436,
     author = {Goode, John B.},
     title = {Accessible Telephone Directories},
     journal = {J. Symbolic Logic},
     volume = {59},
     number = {1},
     year = {1994},
     pages = { 92-105},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183744436}
}

Goode, John B. Accessible Telephone Directories. J. Symbolic Logic, Tome 59 (1994) no. 1, pp.  92-105. http://gdmltest.u-ga.fr/item/1183744436/