PR ≠ NCR

Felipe Cucker

doi:10.1016/0885-064X(92)90024-6

PR ≠ NCR

Felipe Cucker

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

36 Citations (Scopus)

Abstract

In this note, we show the existence of sets of real numbers that can be decided in polynomial time for the Blum, Shub and Smale model of computation but cannot be decided in polylogarithmic parallel time using an arbitrary number of processors. © 1992.

Original language	English
Pages (from-to)	230-238
Journal	Journal of Complexity
Volume	8
Issue number	3
DOIs	https://doi.org/10.1016/0885-064X(92)90024-6
Publication status	Published - Sept 1992
Externally published	Yes

Access Output

10.1016/0885-064X(92)90024-6Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{bf76fb33607440b6a07b9ff8b89ed479,

title = "PR ≠ NCR",

abstract = "In this note, we show the existence of sets of real numbers that can be decided in polynomial time for the Blum, Shub and Smale model of computation but cannot be decided in polylogarithmic parallel time using an arbitrary number of processors. {\textcopyright} 1992.",

author = "Felipe Cucker",

year = "1992",

month = sep,

doi = "10.1016/0885-064X(92)90024-6",

language = "English",

volume = "8",

pages = "230--238",

journal = "Journal of Complexity",

issn = "0885-064X",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - PR ≠ NCR

AU - Cucker, Felipe

PY - 1992/9

Y1 - 1992/9

N2 - In this note, we show the existence of sets of real numbers that can be decided in polynomial time for the Blum, Shub and Smale model of computation but cannot be decided in polylogarithmic parallel time using an arbitrary number of processors. © 1992.

AB - In this note, we show the existence of sets of real numbers that can be decided in polynomial time for the Blum, Shub and Smale model of computation but cannot be decided in polylogarithmic parallel time using an arbitrary number of processors. © 1992.

UR - https://www.scopus.com/pages/publications/0001242490

UR - https://www.scopus.com/pages/publications/0001242490#tab=impact

U2 - 10.1016/0885-064X(92)90024-6

DO - 10.1016/0885-064X(92)90024-6

M3 - RGC 21 - Publication in refereed journal

SN - 0885-064X

VL - 8

SP - 230

EP - 238

JO - Journal of Complexity

JF - Journal of Complexity

IS - 3

ER -

PR ≠ NCR

Abstract

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this