| |
Browse All Reviews > Theory Of Computation (F) > Computation By Abstract Devices (F.1) > Modes Of Computation (F.1.2) > Relativized Computation (F.1.2...)
|
|
 |
|
|
| |
|
|
| |
1-8 of 8
Reviews about "Relativized Computation (F.1.2...)":
|
Date Reviewed |
| |
A shortcut through time: the path to the quantum computer
Johnson G., Vintage Books, 2004. Type: Book (9780375726187)
Quantum computing is a concept proposed by the physicist Richard Feynman, who won the Nobel Prize for Physics in 1965 for his work in the theory of quantum electrodynamics. Feynman is credited with being the first person to suggest tha...
|
Nov 1 2004 |
| |
Quantum computing (natural computing series)
Hirvensalo M., Springer-Verlag, 2004. 214 pp. Type: Book (9783540407041)
A handful of good introductions to ideas in quantum computing--a new, multidisciplinary research area crossing quantum mechanics, theoretical computer science, and mathematics--have appeared in the past few years. Thi...
|
May 28 2004 |
| |
Positive relativizations for log space computability
Toda S. Theoretical Computer Science 77(3): 221-235, 1990. Type: Article
At the beginning of this paper, the author notes that a number of open questions deal with nondeterminism and with the relationship between log space and polynomial time. Over the past 15 years, a succession of seemingly contradictory ...
|
Sep 1 1991 |
| |
The polynomial-time hierarchy and sparse oracles
Balcázar J., Book R. (ed), Schöning U. (ed) Journal of the ACM 33(3): 603-617, 1986. Type: Article
Concerning the question of whether or not the Polynomial Hierarchy (PH) of Meyer and Stockmeyer is indeed an infinite hierarchy of distinct classes, the authors prove:...
|
Dec 1 1987 |
| |
Relativizing complexity classes with sparse oracles
Long T., Selman A. (ed) Journal of the ACM 33(3): 618-627, 1986. Type: Article
This research paper mainly discusses relativations of the following famous open problems: ( 1 ) P = ? NP ( 2 ) NP = ? co-NP ( 3 ) Does the polynomial-time hierarchy collapse?...
|
Apr 1 1987 |
| |
Sparse sets in NP-P: relativizations
Kurtz S. SIAM Journal on Computing 14(1): 113-119, 1985. Type: Article
It is often believed that almost all problems are simple, i.e., problems from NP are hard because they contain difficult instances. This belief is somewhat justified by the fact that good algorithms exist for solving some problems from...
|
Nov 1 1985 |
| |
On relativized polynomial and exponential computations
Heller H. SIAM Journal on Computing 13(4): 717-725, 1984. Type: Article
It is shown that there exists an oracle X that, relative to X nondeterministic exponential computations, yields only the languages in &Sgr;P,X-2- from the polynomial hierarchy. This result is intended to...
|
Jun 1 1985 |
| |
Immunity, relativizations, and nondeterminism
Schoning U., Book R. (ed) SIAM Journal on Computing 13(2): 329-337, 1984. Type: Article
A recent result in the study of relativized complexity classes says that relative to some recursive oracle set A there are sets L in (NP(A) which contain no infinite subset belonging to P(A). (Here NP(A<...
|
Feb 1 1985 |
| |
|
|
| |
|
|
