A motivação para esta pergunta é o fato de que a maioria das strings de n bits é incompressível. Intuitivamente, podemos propor, por analogia, que a maioria das provas de Tautologias seja incompressível para o tamanho polinomial. Basicamente, minha intuição é que algumas provas são inerentemente aleatórias e não podem ser compactadas.
Existe uma boa referência no esforço de pesquisa relacionado ao uso dos resultados da complexidade de Kolmogorov para estabelecer limites inferiores super-polinomiais no tamanho de prova das Tautologias?
Neste Ph.D. dissertação sobre a complexidade dos sistemas de prova proposicional o método Incompressibilidade da Complexidade Kolmogorov é usado para obter o limite inferior Urquhart para uma classe de Tautologias. Gostaria de saber se existem resultados mais fortes usando o método Incompressibilidade ou outros resultados da complexidade de Kolmogorov.
fonte
Respostas:
Arvind, Köbler, Mundhenk e Torán introduziram a noção de complexidade de instância não determinística no tempo. Com base em uma leitura rápida, parece que eles usam a medida de complexidade de Kolmogorov que depende do tamanho da MT não-determinística mais curta. Eles foram capazes de provar a existência de Tautologias difíceis de provar sob uma noção de dureza baseada na complexidade da instância não determinística.
Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán, Complexidade da instância não determinística e tautologias difíceis de provar,
fonte