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

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

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

• 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
• 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?)
• 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 and Distribution of Hard Problems
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Weakly complete problems are not rare
• Weakly Hard Problems
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(9)

• Category and Measure in Complexity Classes
• Measure on P: Robustness of the notion
• scientific article; zbMATH DE number 1335893 (Why is no real title available?)
• Equivalence of Measures of Complexity Classes
• scientific article; zbMATH DE number 1500508 (Why is no real title available?)
• Robust Measures of Information
• Measuring the complexity of reductions between equivalence relations
• Logical Approaches to Computational Barriers
• A note on measuring in P

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)