Accessible telephone directories
- 12 March 1994
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 59 (1) , 92-105
- https://doi.org/10.2307/2275252
Abstract
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.Keywords
This publication has 1 reference indexed in Scilit:
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machinesBulletin of the American Mathematical Society, 1989