Equivalence of Measures of Complexity Classes

DOI10.1137/S0097539796302269MaRDI QIDQ4268882zbMATH OpenFDO

Authors Josef M. Breutzmann, Jack H. Lutz

Publication date 28 October 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539796302269

zbMATH Keywords

complexity classesmartingalesresource-bounded measure

Mathematics Subject Classification ID

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

Recommendations

• Equivalence of measures of complexity classes
• scientific article; zbMATH DE number 1500508
• Resource-bounded measure on probabilistic classes
• scientific article; zbMATH DE number 1335897

Cited in

(10)

• Genericity and randomness over feasible probability measures
• Feasible reductions to Kolmogorov-Loveland stochastic sequences
• 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?)
• scientific article; zbMATH DE number 1500508 (Why is no real title available?)
• Equivalence of measures of complexity classes
• Measuring the complexity of reductions between equivalence relations
• Inseparability and strong hypotheses for disjoint NP pairs
• Resource-bounded measure on probabilistic classes

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 Q4268882)