Applications of Time-Bounded Kolmogorov Complexity in Complexity Theory
- 1 January 1992
- book chapter
- Published by Springer Nature
Abstract
No abstract availableKeywords
This publication has 31 references indexed in Scilit:
- The complexity of computing the number of strings of given length in context-free languagesTheoretical Computer Science, 1991
- On uniformity within NC1Journal of Computer and System Sciences, 1990
- Kolmogorov complexity and degrees of tally setsInformation and Computation, 1990
- Counting problems and algebraic formal power series in noncommuting variablesInformation Processing Letters, 1990
- Some consequences of the existence of pseudorandom generatorsJournal of Computer and System Sciences, 1989
- P-Printable SetsSIAM Journal on Computing, 1988
- Diagonalizations over polynomial time computable setsTheoretical Computer Science, 1987
- On characterizations of the class PSPACE/polyTheoretical Computer Science, 1987
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975