Symmetry of information and nonuniform lower bounds

Sylvain Perifel (1)

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

In a 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]. This method enables us to show a nonuniform lower bound for BPP-consistent languages. 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. 2006. ⟨ensl-00119823v1⟩