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