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).
Type de document :
Pré-publication, Document de travail
12 pages. 2007
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00119823
Contributeur : Sylvain Perifel <>
Soumis le : lundi 4 juin 2007 - 15:40:54
Dernière modification le : mardi 24 avril 2018 - 13:52:23
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 15:47:35

Fichier

sym_info.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-00119823, version 2

Collections

Citation

Sylvain Perifel. Symmetry of information and nonuniform lower bounds. 12 pages. 2007. 〈ensl-00119823v2〉

Partager

Métriques

Consultations de la notice

97

Téléchargements de fichiers

61