Fine separation of average time complexity classes

DOI10.1007/3-540-60922-9_28MaRDI QIDQ4593943zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Alan L. Selman

Publication date 16 November 2017

Published in STACS 96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60922-9_28

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Fine Separation of Average-Time Complexity Classes
• Some Observations on Separating Complexity Classes
• Separation of deterministic, nondeterministic and alternating complexity classes
• scientific article; zbMATH DE number 4077187
• scientific article; zbMATH DE number 2172794
• Separating Complexity Classes Using Autoreducibility
• Average complexity of divide-and-conquer algorithms
• Separating classes in the exponential-time hierarchy from classes in PH
• Separating complexity classes with tally oracles

Cited in

(9)

• An average complexity measure that yields tight hierarchies
• No NP problems averaging over ranking of distributions are harder
• Linear independence of finite Gabor systems determined by behavior at infinity
• Structural Complexity of AvgBPP
• Fine Separation of Average-Time Complexity Classes
• Equivalence of measures of complexity classes
• Rankable distributions do not provide harder instances than uniform distributions
• Reductions and convergence rates of average time
• Structural complexity of AvgBPP

This page was built for publication: Fine separation of average time complexity classes

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