An upward measure separation theorem

DOI10.1016/0304-3975(91)90320-2zbMath0732.68042OpenAlexW1970373826MaRDI QIDQ808696

Jack H. Lutz

Publication date: 1991

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

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90320-2

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

The generic oracle hypothesis is false

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the notion of infinite pseudorandom sequences
• Comparing complexity classes
• Families of recursive predicates of measure zero
• Hardness vs randomness
• Computation times of NP sets of different densities
• Category and Measure in Complexity Classes
• Randomness conservation inequalities; information and independence in mathematical theories
• Algorithms and Randomness
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Computational Complexity of Probabilistic Turing Machines
• On the Length of Programs for Computing Finite Binary Sequences
• A formal theory of inductive inference. Part II
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: An upward measure separation theorem