Genericity and randomness over feasible probability measures

DOI10.1016/S0304-3975(98)00067-XMaRDI QIDQ1275002zbMATH OpenFDO

Authors Amy K. Lorentz, Jack H. Lutz

Publication date 12 January 1999

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(98)00067-X

zbMATH Keywords

resource-bounded genericity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1008512
• scientific article; zbMATH DE number 1492083
• Resource-bounded balanced genericity, stochasticity and weak randomness
• scientific article; zbMATH DE number 1335897

Cites work

• A unified approach to the definition of random sequences
• Almost everywhere high nonuniform complexity
• Diagonalizations over polynomial time computable sets
• Equivalence of Measures of Complexity Classes
• Genericity and measure for exponential time
• scientific article; zbMATH DE number 1048036 (Why is no real title available?)
• scientific article; zbMATH DE number 1072536 (Why is no real title available?)
• scientific article; zbMATH DE number 4121422 (Why is no real title available?)
• scientific article; zbMATH DE number 841081 (Why is no real title available?)
• Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung
• Measure, Stochasticity, and the Density of Hard Languages
• Process complexity and effective random tests
• Resource bounded randomness and weakly complete problems
• Resource-bounded balanced genericity, stochasticity and weak randomness
• The Complexity and Distribution of Hard Problems
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(10)

• Resource-bounded martingales and computable Dowd-type generic sets
• Generic density and small span theorem
• Genericity, Randomness, and Polynomial-Time Approximations
• scientific article; zbMATH DE number 1008512 (Why is no real title available?)
• scientific article; zbMATH DE number 1492083 (Why is no real title available?)
• Resource-bounded balanced genericity, stochasticity and weak randomness
• Genericity and randomness with ITTMs
• Fundamentals of Computation Theory
• Inseparability and strong hypotheses for disjoint NP pairs
• Computable one-way functions on the reals

This page was built for publication: Genericity and randomness over feasible probability measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1275002)