Symmetry of information and nonuniform lower bounds

Sylvain Perifel (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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).

Mots clés: Computational complexity; Nonuniform lower bounds; Resource-bounded Kolmogorov complexity; Symmetry of information

Domaines: Complexité [cs.CC]

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