| |
Browse All Reviews > Theory Of Computation (F) > Computation By Abstract Devices (F.1) > Complexity Measures And Classes (F.1.3) > Relations Among Complexity Classes (F.1.3...)
|
|
 |
|
|
| |
|
|
| |
1-10 of 10
Reviews about "Relations Among Complexity Classes (F.1.3...)":
|
Date Reviewed |
| |
Parallel RAMs with owned global memory and deterministic context-free language recognition
Dymond P., Ruzzo W. Journal of the ACM 47(1): 16-45, 2000. Type: Article
This paper proves a gem of a theorem--one that provides an unexpectedly close connection between a class of formal languages and one type of architecture for parallel algorithms....
|
Jun 1 2000 |
| |
Complexity classes and sparse oracles
Bovet D., Crescenzi P., Silvestri R. Journal of Computer and System Sciences 50(3): 382-390, 1995. Type: Article
One of the problems in complexity theory is that the same types of results seem to be proven over and over for different classes, even though the spirit of the proof is similar for the different classes. It would be natural to seek a n...
|
Sep 1 1996 |
| |
Separation of deterministic, nondeterministic and alternating complexity classes
Bebják A., Štefáneková I. Theoretical Computer Science 88(2): 297-311, 1991. Type: Article
The authors separate nondeterministic and deterministic complexity classes as well as alternating and nondeterministic complexity classes for one-head and multihead Turing machines. In doing so, they consider the product of time and sp...
|
Jan 1 1993 |
| |
Complexity classes defined by counting quantifiers
Torán J. Journal of the ACM 38(3): 752-773, 1991. Type: Article
The counting quantifier C pf, where p is a polynomial and f is an arbitrary function from strings to integers, is defined as follows: C pf y Q ( x , ...
|
Jul 1 1992 |
| |
On the decomposability of NC and AC
Wilson C. SIAM Journal on Computing 19(2): 384-396, 1990. Type: Article
The results given here are very pretty. They relate the power of different circuit-based notions of reducibility. In particular, Wilson shows how the NC and AC hierarchies can be decomposed in a ma...
|
Jun 1 1991 |
| |
On the complexity of theories of permutations
Pelz E. Theoretical Computer Science 41(2-3): 247-269, 1985. Type: Article
In this well-written but quite technical paper, the author considers the logical theory T of two commuting permutations, whose axioms are ( i = 1 , 2 )...
|
Oct 1 1987 |
| |
On bounded query machines
Balcázar J., Book R. (ed), Schöning U. (ed) Theoretical Computer Science 40(2-3): 237-243, 1985. Type: Article
The justification for this paper is that it presents proofs of four existing results on complexity classes in short forms that are technically more accessible than the original proofs (whose sources are cited), and therefore more likel...
|
Jul 1 1987 |
| |
On the structure of one-tape nondeterministic Turing machine time hierarchy
Kobayashi K. Theoretical Computer Science 40(2-3): 175-193, 1985. Type: Article
In the contemporary literature on Turing machine-based complexity theory, properties of acceptable sets with respect to various factors--such as (1) the machine is a deterministic, nondeterministic, or alternating type; (2) th...
|
May 1 1987 |
| |
Computational complexity of sequential and parallel algorithms
Kronsjö L., John Wiley & Sons, Inc., New York, NY, 1986. Type: Book (9789780471908142)
This book consists of two parts, one dealing with computational complexity of sequential algorithms and the other describing computational complexity of parallel algorithms. In many instances, both sequential and parallel algorithms fo...
|
Mar 1 1987 |
| |
Relativizations comparing NP and exponential time
Gasarch W., Homer S. (ed) Information and Control 58(1-3): 88-100, 1984. Type: Article
The authors hold that relationships between deterministic and non-deterministic complexity classes are unsettled. To help settle them, the authors adopt the polynomial time-bounded Turing machines and oracles approach used by others. I...
|
Dec 1 1985 |
| |
|
|
| |
|
|
