Reductions and convergence rates of average time

DOI10.1007/3-540-61332-3_164zbMath1529.68116OpenAlexW1520196288MaRDI QIDQ6184675

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
• Average case completeness
• On the theory of average case complexity
• On average time hierarchies
• On the NP-isomorphism problem with respect to random instances
• Average Case Complete Problems
• Expected Computation Time for Hamiltonian Path problem
• Matrix Transformation Is Complete for the Average Case
• On the Computational Complexity of Algorithms
• The NP-completeness column: An ongoing guide

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