Complexidade de Kolmogorov da concatenação de cadeias

E se $K(s)$ é a complexidade Kolmogorov da cadeia $s \in \{0,1\}^*$ ,

Podemos provar (ou refutar) a seguinte declaração:

"Toda string $s$ é um prefixo de uma string incompressível; ou seja, para cada corda $s$ existe uma string $r$ de tal modo que $K(sr) \geq |sr|$ "?

De uma maneira muito informal (e talvez não muito significativa): sabemos que $K(r) \leq |r| + O(1)$ ; se escolhermos uma string incompressível grande o suficiente $r$ , podemos "usar" o $O(1)$ para "mascarar" a compressibilidade da sequência especificada $s$ ?

Um resultado semelhante (mas diferente) é o de qualquer $c$ , podemos encontrar $s$ e $r$ de tal modo que: $K(sr) > K(s) + K(r) + c$

computability kolmogorov-complexity Vor
fonte

Incomprimível significa que o comprimento da string

s

$s$ é um limite inferior em sua descrição mais curta

K (s)

$K(s)$ ?

saadtaame 16/09/12

@saadtaame: significa que

K (s) \geq | s |

$K(s) \geq |s|$

Vor

Respostas:

Sua conjectura está errada. Para algumas constantes $C,D$ , sustenta que $K(sr) \leq 2K(s) + K(r) + C \leq 2K(s) + |r| + D$ (prova: use uma máquina universal de Turing para gerar $s$ e depois $r$ ; você precisa de um pouco mais do que $K(s)+K(r)$ para armazenar os dois programas, embora $2K(s)+K(r)$ é um exagero). Portanto, se $2K(s) + D < |s|$ , sua conjectura não se sustenta. Cordas tão fáceis $s$ certamente existem, por exemplo $K(0^n) = O(\log n)$ .

Yuval Filmus
fonte

parece ok. Eu pensei que

D

$D$ depende de

r

$r$ , mas uma vez corrigido o UTM, é uma constante. Outra consideração: ao concatenar as duas cadeias, é necessário adicionar

\log | s |

$\log |s|$ bits (para delimitar o programa para

s

$s$ do programa para

r

$r$ ), para que sua prova não funcione se modificarmos a "conjectura" em: "toda string incompressível

s

$s$ é um prefixo de uma sequência incompressível

r

$r$ "? Você consegue ver como (des) provar isso com facilidade?"

Vor

A última conjectura é menos interessante, pois

s

$s$ já é incompressível. Formalmente, você pode escolher

r = s

$r = s$ , embora seja fácil impedir essa solução.

Yuval Filmus

@Yuval Filmus, você tem alguma idéia de como provar a segunda afirmação, ou seja, para qualquer

c

$c$ , podemos encontrar

s

$s$ e

r

$r$ de tal modo que:

K (s r) > K (s) + K (r) + c

$K(sr)>K(s)+K(r)+c$ Isso é afirmado no livro de Sipser e deixado como um problema de exercício, mas não pude provar isso e estou muito curioso para saber que tipo de técnica de prova deve ser usada para mostrar esse resultado. Obrigado!

Han Zhao

Sugiro que você publique isso como uma nova pergunta com o botão 'Fazer pergunta'. Quando você faz isso, pode ajudar se você nos disser quais abordagens você tentou. Definitivamente não pertence como resposta aqui.