Equivalence of measures of complexity classes

DOI10.1007/BFB0023487MaRDI QIDQ5048952zbMATH OpenOpenAlexFDO

Authors Josef M. Breutzmann, Jack H. Lutz

Publication date 9 November 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0023487

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Equivalence of Measures of Complexity Classes
• Category and Measure in Complexity Classes
• scientific article; zbMATH DE number 1500508
• Logical Approaches to Computational Barriers
• Resource-bounded measure on probabilistic classes

Cites work

• scientific article; zbMATH DE number 4054673 (Why is no real title available?)
• scientific article; zbMATH DE number 3678157 (Why is no real title available?)
• scientific article; zbMATH DE number 1261804 (Why is no real title available?)
• scientific article; zbMATH DE number 3446413 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3060775 (Why is no real title available?)
• A unified approach to the definition of random sequences
• Almost every set in exponential time is P-bi-immune
• Almost everywhere high nonuniform complexity
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Families of recursive predicates of measure zero
• Fine separation of average time complexity classes
• Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung
• Measure, Stochasticity, and the Density of Hard Languages
• Observations on measure and lowness for \(\Delta_2^{\mathrm{P}}\) (extended abstract)
• On equivalence of infinite product measures
• Process complexity and effective random tests
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The Complexity and Distribution of Hard Problems
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Weakly Hard Problems
• Weakly complete problems are not rare
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(6)

• Category and Measure in Complexity Classes
• Measure on P: Robustness of the notion
• A note on measuring in P
• Measuring the complexity of reductions between equivalence relations
• Logical Approaches to Computational Barriers
• Robust Measures of Information

This page was built for publication: Equivalence of measures of complexity classes

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