Symmetry of information and nonuniform lower bounds

Abstract : In the first part we provide another proof of the result of [Homer, Mocas 1995] that for all constant c, the class EXP is not included in P/(n^c) . The proof is based on a simple diagonalization, whereas it uses resource-bounded Kolmogorov complexity in [Homer, Mocas 1995]. In the second part, we investigate links between resource-bounded Kolmogorov complexity and nonuniform classes in computational complexity. Assuming a version of polynomial-time symmetry of information, we show that exponential-time problems do not have polynomial-size circuits (in symbols, EXP is not included in P/poly).
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00119823
Contributor : Sylvain Perifel <>
Submitted on : Monday, June 4, 2007 - 3:40:54 PM
Last modification on : Tuesday, April 24, 2018 - 1:52:23 PM
Long-term archiving on : Friday, November 25, 2016 - 3:47:35 PM

File

sym_info.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ensl-00119823, version 2

Collections

Citation

Sylvain Perifel. Symmetry of information and nonuniform lower bounds. 2007. ⟨ensl-00119823v2⟩

Share

Metrics

Record views

129

Files downloads

142