Almost everywhere high nonuniform complexity

DOI10.1016/0022-0000(92)90020-JzbMath0767.68043MaRDI QIDQ1190985

Jack H. Lutz

Publication date: 27 September 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

lower boundspseudorandom sequencescircuit-size complexitynonuniform complexitiesselective Kolmogorov complexityuniform complexity classes

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (86)

Computational depth and reducibility ⋮ Scaled dimension and nonuniform complexity ⋮ Computational depth and reducibility ⋮ NP-hard sets are superterse unless NP is small ⋮ Unnamed Item ⋮ Relative to a random oracle, P/poly is not measurable in EXP ⋮ A separation of two randomness concepts ⋮ Equivalence of measures of complexity classes ⋮ An outer-measure approach for resource-bounded measure ⋮ Unnamed Item ⋮ Almost every set in exponential time is P-bi-immune ⋮ Genericity and measure for exponential time ⋮ A zero-one law for RP and derandomization of AM if NP is not small ⋮ An excursion to the Kolmogorov random strings ⋮ Schnorr randomness ⋮ On the construction of effectively random sets ⋮ Measure on \(P\): Strength of the notion ⋮ Nonuniform reductions and NP-completeness ⋮ Weakly useful sequences ⋮ Index sets and presentations of complexity classes ⋮ Lines missing every random point1 ⋮ A note on measuring in P ⋮ The size of SPP ⋮ Recursive computational depth ⋮ Results on resource-bounded measure ⋮ Weakly complete problems are not rare ⋮ Comparing reductions to NP-complete sets ⋮ On the relative sizes of learnable sets ⋮ Functions that preserve p-randomness ⋮ Normal numbers and sources for BPP ⋮ Resource bounded randomness and weakly complete problems ⋮ An oracle builder's toolkit ⋮ Dimension and the structure of complexity classes ⋮ A zero-one SUBEXP-dimension law for BPP ⋮ Feasible reductions to Kolmogorov-Loveland stochastic sequences ⋮ Dimension, halfspaces, and the density of hard sets ⋮ Base invariance of feasible dimension ⋮ Hard sets are hard to find ⋮ Almost complete sets. ⋮ Martingale families and dimension in P ⋮ Cook versus Karp-Levin: Separating completeness notions if NP is not small ⋮ Effective category and measure in abstract complexity theory ⋮ Weak completeness in \(\text{E}\) and \(\text{E}_{2}\) ⋮ Upward separations and weaker hypotheses in resource-bounded measure ⋮ Measure, category and learning theory ⋮ Generic density and small span theorem ⋮ Baire categories on small complexity classes and meager-comeager laws ⋮ Schnorr Randomness ⋮ Nondeterminisic sublinear time has measure 0 in P ⋮ A Characterization of Constructive Dimension ⋮ 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 ⋮ Circuit size relative to pseudorandom oracles ⋮ Effective category and measure in abstract complexity theory ⋮ On pseudorandomness and resource-bounded measure ⋮ Dimension, entropy rates, and compression ⋮ Weakly useful sequences ⋮ A note on dimensions of polynomial size circuits ⋮ Quantitative aspects of speed-up and gap phenomena ⋮ Strong Reductions and Isomorphism of Complete Sets ⋮ Generalised and quotient models for random and/or~trees and application to satisfiability ⋮ A characterization of constructive dimension ⋮ Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds ⋮ Gales suffice for constructive dimension ⋮ Dimension extractors and optimal decompression ⋮ Polylog depth, highness and lowness for E ⋮ Axiomatizing Resource Bounds for Measure ⋮ On the robustness of ALMOST-$\mathcal {R}$ ⋮ On the size of classes with weak membership properties ⋮ Genericity and randomness over feasible probability measures ⋮ Almost every set in exponential time is P-bi-immune ⋮ Genericity and measure for exponential time ⋮ Resource bounded randomness and computational complexity ⋮ Complete distributional problems, hard languages, and resource-bounded measure ⋮ The zero-one law holds for BPP ⋮ Calibrating Randomness ⋮ Genericity, Randomness, and Polynomial-Time Approximations ⋮ Reviewing bounds on the circuit size of the hardest functions ⋮ Resource-bounded strong dimension versus resource-bounded category ⋮ MAX3SAT is exponentially hard to approximate if NP has positive dimension. ⋮ Recursive computational depth. ⋮ Resource-bounded martingales and computable Dowd-type generic sets ⋮ Feasible analysis, randomness, and base invariance ⋮ A stronger Kolmogorov zero-one law for resource-bounded measure

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kolmogorov complexity and degrees of tally sets
• Relativized circuit complexity
• On the notion of infinite pseudorandom sequences
• One way functions and pseudorandom generators
• Families of recursive predicates of measure zero
• Computation times of NP sets of different densities
• Sets with small generalized Kolmogorov complexity
• Some consequences of the existnce of pseudorandom generators
• Process complexity and effective random tests
• Pseudorandom sources for BPP
• Circuit-size lower bounds and non-reducibility to sparse sets
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Can an individual sequence of zeros and ones be random?
• Category and Measure in Complexity Classes
• The complexity of information extraction
• Some Observations about the Randomness of Hard Problems
• Von Mises' definition of random sequences reconsidered
• Algorithms and Randomness
• Classes of computable functions defined by bounds on computation
• On the Length of Programs for Computing Finite Binary Sequences
• [https://portal.mardi4nfdi.de/wiki/Publication:5587565 Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung]
• Complexity oscillations in infinite binary sequences
• A unified approach to the definition of random sequences
• The definition of random sequences
• A formal theory of inductive inference. Part II

This page was built for publication: Almost everywhere high nonuniform complexity