scientific article; zbMATH DE number 1072536
From MaRDI portal
Publication:4359463
zbMATH Open0880.68044MaRDI QIDQ4359463FDOQ4359463
Publication date: 8 October 1997
Title of this publication is not available (Why is that?)
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Cited In (36)
- Functions that preserve p-randomness
- Process and truth-table characterisations of randomness
- Comparing nontriviality for E and EXP
- A stronger Kolmogorov zero-one law for resource-bounded measure
- Inseparability and strong hypotheses for disjoint NP pairs
- An outer-measure approach for resource-bounded measure
- Dimension, halfspaces, and the density of hard sets
- Comparing reductions to NP-complete sets
- Dimension and the structure of complexity classes
- Hard Instances of Algorithms and Proof Systems
- Genericity and randomness over feasible probability measures
- Upward separations and weaker hypotheses in resource-bounded measure
- Relative to a random oracle, P/poly is not measurable in EXP
- A note on measuring in P
- The size of SPP
- Generic density and small span theorem
- A characterization of constructive dimension
- Title not available (Why is that?)
- Polylog depth, highness and lowness for E
- Almost complete sets.
- Complete distributional problems, hard languages, and resource-bounded measure
- The zero-one law holds for BPP
- Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998
- Relativized worlds with an infinite hierarchy
- Computability versus exact computability of martingales
- The complexity of stochastic sequences
- Dimension is compression
- Nondeterminisic sublinear time has measure 0 in P
- Dimension, entropy rates, and compression
- General exponential dichotomies: from finite to infinite time
- A zero-one law for RP and derandomization of AM if NP is not small
- Genericity and measure for exponential time
- Martingale families and dimension in P
- Resource-bounded measure on probabilistic classes
- Some implications of a new approach to exponential functions on time scales
- Nonuniform reductions and NP-completeness
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4359463)
