Name
Abstract | ||
|---|---|---|
It is well-known that the class P=poly can be characterized in terms of polynomialsize circuits. We obtain a characterization of the class P= log using polynomialsize circuits with low resource-bounded Kolmogorov Complexity.The concept of "small circuits with easy descriptions" has been introduced inthe literature as a candidate to characterizing P= log. We prove that this conceptcorresponds exactly to the class P=O(log n log(log n)), and that this is differentfrom P= log.... |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1007/BF01192144 | Mathematical Systems Theory |
Keywords | Field | DocType |
Computational Mathematic,Kolmogorov Complexity,Small Circuit | Discrete mathematics,Combinatorics,Kolmogorov complexity,Polynomial,P,Kolmogorov structure function,Electronic circuit,Chain rule for Kolmogorov complexity,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
27 | 4 | 0025-5661 |
Citations | PageRank | References |
4 | 0.46 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Montserrat Hermo | 1 | 55 | 10.77 |
| Elvira Mayordomo | 2 | 500 | 39.46 |