An upward measure separation theorem

DOI10.1016/0304-3975(91)90320-2zbMATH Open0732.68042OpenAlexW1970373826MaRDI QIDQ808696FDOQ808696

Authors: 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

Recommendations

• Category and Measure in Complexity Classes
• Resource-bounded measure on probabilistic classes
• Upward separations and weaker hypotheses in resource-bounded measure
• scientific article; zbMATH DE number 1346358
• scientific article; zbMATH DE number 1500508
• Martingale families and dimension in P
• A stronger Kolmogorov zero-one law for resource-bounded measure
• scientific article; zbMATH DE number 1335897
• Logical Approaches to Computational Barriers
• Relative to a random oracle, NP is not small

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• Upward separations and weaker hypotheses in resource-bounded measure
• The generic oracle hypothesis is false
• A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem

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

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