Equivalence of measures of complexity classes

DOI10.1007/BFB0023487zbMATH Open1498.68114OpenAlexW2161147766MaRDI QIDQ5048952FDOQ5048952

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

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

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)

Cites Work

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

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)