scientific article; zbMATH DE number 1072536

MaRDI QIDQ4359463zbMATH OpenFDO

Authors Jack H. Lutz

Publication date 8 October 1997

zbMATH Keywords

bi-immunitycomplexity coresexponential time complexity classesKolmogorov complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Genericity and measure for exponential time
• The Complexity and Distribution of Hard Problems
• Genericity and measure for exponential time (extended abstract)
• scientific article; zbMATH DE number 1759402

Cited in

(36)

• Genericity and randomness over feasible probability measures
• Genericity and measure for exponential time
• Almost complete sets.
• Complete distributional problems, hard languages, and resource-bounded measure
• The zero-one law holds for BPP
• Relativized worlds with an infinite hierarchy
• General exponential dichotomies: from finite to infinite time
• A stronger Kolmogorov zero-one law for resource-bounded measure
• Dimension is compression
• Nondeterminisic sublinear time has measure 0 in P
• Nonuniform reductions and NP-completeness
• Some implications of a new approach to exponential functions on time scales
• Polylog depth, highness and lowness for E
• A zero-one law for RP and derandomization of AM if NP is not small
• Upward separations and weaker hypotheses in resource-bounded measure
• The complexity of stochastic sequences
• Generic density and small span theorem
• Dimension, entropy rates, and compression
• Relative to a random oracle, P/poly is not measurable in EXP
• Nonuniform reductions and NP-completeness
• A characterization of constructive dimension
• Genericity and measure for exponential time (extended abstract)
• Hard instances of algorithms and proof systems
• Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998
• A note on measuring in P
• The size of SPP
• Dimension and the structure of complexity classes
• Dimension, halfspaces, and the density of hard sets
• Comparing nontriviality for E and EXP
• Inseparability and strong hypotheses for disjoint NP pairs
• Process and truth-table characterisations of randomness
• Computability versus exact computability of martingales
• An outer-measure approach for resource-bounded measure
• Comparing reductions to NP-complete sets
• Martingale families and dimension in P
• Resource-bounded measure on probabilistic classes

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)