Reductions and convergence rates of average time

DOI10.1007/3-540-61332-3_164zbMATH Open1529.68116OpenAlexW1520196288MaRDI QIDQ6184675FDOQ6184675

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

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

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)