Genericity and randomness over feasible probability measures

DOI10.1016/S0304-3975(98)00067-XzbMath0912.68107MaRDI QIDQ1275002

Jack H. Lutz, Amy K. Lorentz

Publication date: 12 January 1999

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

zbMATH Keywords

resource-bounded genericity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Generic density and small span theorem ⋮ Inseparability and strong hypotheses for disjoint NP pairs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Diagonalizations over polynomial time computable sets
• Almost everywhere high nonuniform complexity
• Genericity and measure for exponential time
• Resource bounded randomness and weakly complete problems
• Process complexity and effective random tests
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Equivalence of Measures of Complexity Classes
• Measure, Stochasticity, and the Density of Hard Languages
• Resource-bounded balanced genericity, stochasticity and weak randomness
• The Complexity and Distribution of Hard Problems
• [https://portal.mardi4nfdi.de/wiki/Publication:5587565 Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung]
• A unified approach to the definition of random sequences

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