Symmetry of Information and Nonuniform Lower Bounds

DOI10.1007/978-3-540-74510-5_32zbMath1188.68148OpenAlexW1771461475MaRDI QIDQ3499781

Sylvain Perifel

Publication date: 3 June 2008

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://hal-ens-lyon.archives-ouvertes.fr/ensl-00119823v2/file/sym_info.pdf

zbMATH Keywords

computational complexitysymmetry of informationnonuniform lower boundsresource-bounded Kolmogorov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

This page was built for publication: Symmetry of Information and Nonuniform Lower Bounds