Reductions and convergence rates of average time

DOI10.1007/3-540-61332-3_164MaRDI QIDQ6184675zbMATH OpenOpenAlexFDO

Authors Jay Belanger, Jie Wang

Publication date 29 January 2024

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

Full work available at URL https://doi.org/10.1007/3-540-61332-3_164

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Reductions do not preserve fast convergence rates in average time
• Structural average case complexity
• Fine Separation of Average-Time Complexity Classes
• Fine separation of average time complexity classes
• scientific article; zbMATH DE number 512870

Cites work

• scientific article; zbMATH DE number 1263208 (Why is no real title available?)
• scientific article; zbMATH DE number 512799 (Why is no real title available?)
• scientific article; zbMATH DE number 1072538 (Why is no real title available?)
• scientific article; zbMATH DE number 4779 (Why is no real title available?)
• A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
• Average Case Complete Problems
• Average case completeness
• Expected Computation Time for Hamiltonian Path problem
• Matrix Transformation Is Complete for the Average Case
• On average time hierarchies
• On the Computational Complexity of Algorithms
• On the NP-isomorphism problem with respect to random instances
• On the theory of average case complexity
• The NP-completeness column: An ongoing guide

This page was built for publication: Reductions and convergence rates of average time

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