| |
Browse All Reviews > Theory Of Computation (F) > Computation By Abstract Devices (F.1) > Complexity Measures And Classes (F.1.3) > Relations Among Complexity Measures (F.1.3...)
|
|
 |
|
|
| |
|
|
| |
1-4 of 4
Reviews about "Relations Among Complexity Measures (F.1.3...)":
|
Date Reviewed |
| |
On the relative strength of pebbling and resolution
Nordström J. ACM Transactions on Computational Logic 13(2): 1-43, 2012. Type: Article
Resolution refutation can beat black-only pebbling. This is the main result of this paper....
|
Jul 9 2012 |
| |
Contention in shared memory algorithms
Dwork C., Herlihy M., Waarts O. Journal of the ACM 44(6): 779-805, 1997. Type: Article
It is well known that, in practice, the performance of shared memory multiprocessors can degrade severely in the presence of contention, which occurs when multiple processors access the same memory location concurrently. In this paper,...
|
Jun 1 1998 |
| |
The difference between one tape and two tapes: with respect to reversal complexity
Chen J. Theoretical Computer Science 73(3): 265-278, 2001. Type: Article
The number of head reversals made during a Turing machine computation is being studied by a number of researchers as a measure of the complexity of the computation. This measure is considered important because of its relationship to ...
|
Jul 1 1991 |
| |
Relativized circuit complexity
Wilson C. Journal of Computer and System Sciences 31(2): 169-181, 1985. Type: Article
This work is another contribution to the goal of obtaining new techniques for relating Turing machine time, a uniform measure, versus Boolean circuit size, a nonuniform measure. Using “an intrinsically circuit-based oracle mo...
|
May 1 1987 |
| |
|
|
| |
|
