Average case complexity theory

DOI10.35834/2025/3701079MaRDI QIDQ6976876zbMATH OpenFDO

Authors Sriram Venkatesh

Publication date 31 May 2025

Published in Missouri Journal of Mathematical Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.35834/2025/3701079

zbMATH Keywords

complexity theoryreducibilitybounded halting problemdistributional problemsCook-Levin theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• All natural NP-complete problems have average-case complete versions
• Average Case Complete Problems
• Notes on Levin's theory of average-case complexity
• On the Computational Complexity of Algorithms
• Paths, Trees, and Flowers
• The complexity of theorem-proving procedures

This page was built for publication: Average case complexity theory

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