| |
Browse All Reviews > Theory Of Computation (F) > Computation By Abstract Devices (F.1) > Complexity Measures And Classes (F.1.3) > Complexity Hierarchies (F.1.3...)
|
|
 |
|
|
| |
|
|
| |
1-10 of 12
Reviews about "Complexity Hierarchies (F.1.3...)":
|
Date Reviewed |
| |
The complexity of reasoning with FODD and GFODD
Hescott B., Khardon R. Artificial Intelligence 2291-32, 2015. Type: Article
First-order logic in a logical language invites undecidable complexity of inference irrespective of the language’s restrictions. First-order decision diagrams (FODDs) and generalized first-order decision diagrams (GFODDs) rep...
|
Apr 26 2016 |
| |
Verifying time complexity of Turing machines
Gajser D. Theoretical Computer Science 600(C): 86-97, 2015. Type: Article
For any function T, consider the following decision problem HALTT: does a given Turing machine M run in time at most T(n)? More g...
|
Dec 8 2015 |
| |
Computational complexity: a quantitative perspective
Zimand M., Elsevier Science Inc., Burlington, MA, 2004. 352 pp. Type: Book (9780444828415)
Computational complexity has been studied for a long time and in a lot of detail. However, in this book, Zimand manages to contribute an abundance of novel resulotts and new perspectives on old problems. Zimand’s approach...
|
Nov 3 2005 |
| |
Current trends in theoretical computer science algorithms and complexity, vol. 1
Paun G., Rozenberg G., Salomaa A., World Scientific Press, Hackensack, NJ, 2004. 660 pp. Type: Book (9789812389664)
Algorithmics, complexity, distributed computing, and natural computing--all areas of theoretical computer science-- are discussed in this collection of short survey papers. All of the papers have been extracted (some ...
|
Jun 20 2005 |
| |
Gap-languages and log-time complexity classes
Regan K., Vollmer H. Theoretical Computer Science 188(1-2): 101-116, 1997. Type: Article
Notions of log-time many-one reductions are investigated. These reductions are very restrictive, and are thus ideally suited for studying very low complexity classes. For instance, uniformity notions for circuit classes below LOGSPACE ...
|
Apr 1 1999 |
| |
Communication complexity
Kushilevitz E., Nisan N., Cambridge University Press, New York, NY, 1997. Type: Book (9780521560672)
The communication complexity of two-party protocols was introduced by Abelson [1] and Yao [2] in 1978 and 1979. The initial goal was to develop a method for proving lower bounds on the complexity of distributed and parallel computation...
|
Dec 1 1998 |
| |
A communication hierarchy of parallel computations
Geffert V. Theoretical Computer Science 198(1-2): 99-130, 1998. Type: Article
The notion of synchronized alternation is extended and generalized in this appropriately titled paper on computational complexity. The nature of message broadcasting is shown to be nondeterministic, so a new computational model, commun...
|
Nov 1 1998 |
| |
Some hierarchies for the communication complexity measures of cooperating grammar systems
Hromkovič J., Kari J., Kari L. Theoretical Computer Science 127(1): 123-147, 1994. Type: Article
The structure of the communication graph and the number of communication steps are two new complexity measures defined for parallel communicating grammar systems (PCGSs); PCGSs were introduced in Paun and Santean [1]. Only PCGSs with r...
|
Dec 1 1995 |
| |
Unambiguity of circuits
Lange K. Theoretical Computer Science 107(1): 77-94, 1993. Type: Article
The author considers the concept of unambiguity of circuits and studies several classes of unambiguous circuit families within the NC-hierarchy. In particular, he answers an open question from L. Stockmeyer and C. Vishkin [1] character...
|
May 1 1994 |
| |
The membership problem in aperiodic transformation monoids
Beaudry M., McKenzie P., Thérien D. Journal of the ACM 39(3): 599-616, 1992. Type: Article
The computational complexity of the membership problem for a subset V of the class of all finite aperiodic monoids is studied. The results are the following. With one family of NP-hard exceptions whose exact status is still u...
|
Dec 1 1993 |
| |
|
|
| |
|
|
