Limites inferiores do circuito e complexidade kolmogorov

Considere o seguinte raciocínio:

Seja denotado a complexidade de Kolmogorov da cadeia . O teorema da incompletude de Chaitin diz que $K(x)$ $x$

para qualquer sistema formal consistente e suficientemente forte , existe uma constante (dependendo apenas do sistema formal e sua linguagem) de tal forma que para quaisquer cordas , não pode provar que . $S$ $T$ $x$ $S$ $K(x) \geq T$

Seja uma função booleana em variáveis; a complexidade Kolmogorov de seu espectro é no máximo . Seja a complexidade do circuito de , ou seja, o tamanho do circuito mínimo que computa . $f_n$ $n$ $k$ $S(f_n)$ $f_n$ $f_n$

Um limite superior aproximado para é para uma constante e é uma função de castor ocupado (o máximo possível de etapas para uma parada) A máquina de Turing com uma descrição do tamanho pode ser executada). (Para cada no espectro, construa o mintermo da atribuição de verdade correspondente e leve OU de todos esses mintermos juntos.) $S(f_n)$

S (f_{n}) \leq c \cdot B B (k) \cdot n

$S(f_n)\leq c\cdot BB(k) \cdot n$

c

$c$

B B (k)

$BB(k)$

k

$k$

1

$1$

Suponha agora que, para uma família infinita de funções booleanas $L = \{f_n\}_{n}$ , tenhamos uma prova formal de que $L$ requer circuitos de tamanho superlinear, ou seja,

S ⊢ \forall n \geq n_{0 0}, g (n) \cdot n \leq S (f_{n})

$S \vdash \forall n \geq n_0, \ g(n)\cdot n \leq S(f_n)$ que

g (n) \in ω (1)

$g(n)\in \omega(1)$ .

Se considerarmos que $n$ é suficientemente grande, teremos

g (n) > c \cdot B B (T)

$g(n) > c\cdot BB(T)$

Em particular, isso seria uma prova de que a complexidade Kolmogorov do espectro de $f_n$ é pelo menos $T$ , o que é impossível.

Isso leva a duas perguntas:

1) Deve haver algo errado no raciocínio acima. Principalmente porque isso tornaria os limites inferiores do circuito superlinear formalmente inviáveis.

2) Você conhece abordagens semelhantes para mostrar barreiras para limites inferiores, ou seja, mostrando que certos tipos de limites inferiores (de circuito) são formalmente improváveis?

cc.complexity-theory reference-request lo.logic circuit-complexity kolmogorov-complexity Magnus Find
fonte

idéias interessantes. um pouco relacionado à prova de razborov / rudich, "provas naturais" que esboçam barreiras ao P =? NP (mas também provavelmente aplicáveis a outras separações de classes de complexidade, conforme listadas como exemplos no artigo) .. você leu esse artigo? veja também barreiras P =? NP e barreiras / complexidade de circuitos monótonos . Parece que as separações de classes de complexidade são semelhantes em estrutura às provas de improvabilidade.

vzn

você pode elaborar sobre o "espectro" de f_n? existe uma maneira de formular a pergunta sem se referir ao "espectro"?

vzn

provavelmente é verdade que se pode estudar a complexidade das funções estudando a menor MT [no sentido de tabela / estados de estados] que as calcula e que isso corresponderá aproximadamente aos limites inferiores do circuito. se você puder mostrar que é impossível, e não muito difícil, encontrar a menor MT, você pode ter alguma coisa lá. no entanto, é "simples" encontrar a menor MT através da enumeração canônica de circuitos ou MTs. se você ponderar por que essa abordagem funciona, pode ser útil entender por que a pergunta não leva a um problema.

vzn

Direita. Obrigado pelas referências. Eu sei sobre o artigo de Provas Naturais. Não sei se a pergunta pode ser formulada sem "espectro". O que quero dizer com "espectro" é a sequência

(f (0, 0, . ., 0), f (0, 0, . ., 1), . ., f (1, 1, . ., 1))

$(f(0,0,..,0),f(0,0,..,1),..,f(1,1,..,1))$

Magnus Encontre

Respostas:

Não há nada errado com o seu argumento, mas não há contradição. Você provar que de algum grande o suficiente a complexidade de Kolmogorov do espectro de é sempre pelo menos . Mas essa afirmação é trivialmente verdadeira! Embora não possamos provar que a complexidade de Kolmogorov de uma cadeia é grande, se tivermos uma sequência, a partir de algum ponto ela deverá conter apenas cadeias de grande complexidade. Então, o que é esse que você tem? Ele deve satisfazer , que é um número que não podemos computar (por causa do ); portanto, não há nenhum problema. $N$ $f_n$ $T$ $N$ $N>g^{-1}(c \cdot BB(T))$ $BB$

domotorp
fonte

Obrigado. Caí na armadilha de acreditar que alguém poderia "escolher" algum valor de N suficientemente grande, mas, como você ressalta, isso não é possível em e, como você também indica corretamente, isso seria de fato verdade para qualquer família de sequências crescentes.

S

$S$

Magnus Encontre

Aqui está uma situação problemática ainda mais simples. Seja a primeira cadeia (em ordem lexicográfica) tal que ; essa cadeia existe provavelmente para todos os . Então . $A(k)$ $K(A(k)) \geq k$ $k$ $K(A(k)) \geq k$

O culpado pode ser que o sistema formal não possa computar . $BB(T)$

Edit: Aqui está uma situação problemática "mais explícita". Seja o comprimento máximo de uma cadeia cuja complexidade de Kolmogorov seja no máximo ; existe comprovadamente. Então . $\alpha(k)$ $k$ $\alpha(k)$ $K(0^{\alpha(k)+1}) > k$

Yuval Filmus
fonte

Por que essa situação é problemática? Você não forneceu um programa cuja saída seria A (k) e seu comprimento seria menor que k.

Domotorp

Tenho a mesma confusão que Domotor, mas concordo que um problema com o raciocínio do OP é que um sistema formal não será capaz de provar limites superiores no para suficientemente grande .

B B (k)

$BB(k)$

k

$k$

22812 Sasso Nikolov

É problemático (sem dúvida) no mesmo sentido que a pergunta original.

Yuval Filmus

Eu ainda não entendi. Você não exibe uma sequência e uma prova de que a complexidade de Kolmogorov é grande. Você exibe uma prova de que existe uma cadeia cuja complexidade é grande.

Sasho Nikolov

Eu acho que eles são problemáticos de maneiras diferentes. Enquanto eu o leio, você aponta para uma afirmação verdadeira específica, que não possui uma prova. Conforme expus na minha pergunta, aponto que isso implica uma prova de algo que não é comprovável.

Magnus Encontre