Fine separation of average time complexity classes

DOI10.1007/3-540-60922-9_28zbMath1379.68139OpenAlexW1702487489MaRDI QIDQ4593943

Selman, Alan L., Jin-Yi Cai

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)

Related Items (4)

Equivalence of measures of complexity classes ⋮ No NP problems averaging over ranking of distributions are harder ⋮ Rankable distributions do not provide harder instances than uniform distributions ⋮ Linear independence of finite Gabor systems determined by behavior at infinity

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