Usando a complexidade de Kolmogorov como "tamanho" de entrada

21

Digamos que temos um problema computacional, por exemplo, 3-SAT, que tem um conjunto de instâncias de problemas (possíveis entradas) . Normalmente, na análise de algoritmos ou teoria da complexidade computacional, temos alguns conjuntos de todas as entradas de comprimento e uma função que fornece o tempo de execução de algum algoritmo de solução na entrada . A pior sequência de tempo de execução para é então I ( n ) = { w S : | w | = n } n T ( w ) A w A f n = max w I ( n ) T ( w ) .S

I(n)={wS:|w|=n}
nT(w)AwA
fn=maxwI(n)T(w).

Vamos agora definir os conjuntos de todas as entradas com complexidade Kolmogorov e definir a sequência Aqui é a sequência média de tempo de execução para , exceto onde o "tamanho" das entradas é a complexidade de Kolmogorov, não o comprimento.n f K n = 1

IK(n)={wS:K(w)=n}
nfKA
fnK=1|IK(n)|wIK(n)T(w).
fKA

Existem algoritmos para os quais é assintoticamente significativamente diferente de ? Em caso afirmativo, existem problemas cuja complexidade de tempo muda ao usar essa maneira diferente de analisar algoritmos?f K nfnfnK

Andrew
fonte
4
Ótima pergunta! Um que eu sempre me perguntei - espero que receba boas respostas. (I adicionado a etiqueta parametrizado-complexidade b / c que possa ver esta como a causa da complexidade parametrizado de sab por exemplo, onde o parâmetro é a complexidade de Kolmogorov.)
Joshua Grochow
3
Seqüências de caracteres aleatórias, também conhecidas como a maioria das strings, têm complexidade Kolmogorov próximo ao seu comprimento original. Para a grande maioria das entradas Você pode obter um resultado mais interessante se perguntar sobre a profundidade computacional em vez da complexidade de Kolmogorov. google.com/…fn=fnK
Chad Brewbaker,
2
Misturando algumas instâncias do PARITY em um idioma rígido para formar (por exemplo, prefixando cada instância com um pouco de alternância que descreva de qual idioma a instância é), então será menor que . O quão pequeno depende da densidade relativa. f K n f nSfnKfn
András Salamon
1
Um lugar está nas notas de aula de Vadhan aqui (19 de fevereiro): people.seas.harvard.edu/~salil/cs221/spring10/lectures.html
usul
1
@ AndrásSalamon, sim, espero não estar sendo muito desleixado, mas acho quedeve ser essencialmente a função de ocupado-castor. nmaxw:K(w)=n|w|
usul 28/02

Respostas:

14

Considere a função de paridade (ou qualquer outra função que dependa de todos / a maioria dos bits da entrada). Para a função de paridade, . Então Por outro lado, T(w)=Θ(|w|)

fn=Θ(n).
fnK=Θ(1|IK(n)|w:K(w)=n|w|)Ω(12nmaxw:K(w)=n|w|).

Observe que . Assim e . Da mesma forma, ; assim “cresce muito rapidamente”. Além disso, não é difícil ver que não há computável limite superior para .K(22n)=O(n)

maxw:K(w)=n|w|22Ω(n)
fnK22Ω(n)/2nK(222n)=O(n)fnK222Ω(n)/2nfnK
Yury
fonte
9

Dado o interesse por essa pergunta, achei que seria útil apontar mais explicitamente a razão pela qual não devemos nos surpreender com a resposta e tentar dar alguma orientação para aprimoramentos da pergunta. Isso coleta e expande alguns comentários. Peço desculpas se isso é "óbvio"!

Considere o conjunto de cadeias de caracteres de complexidade Kolmogorov : Existem no máximo dessas strings, pois existem descrições de comprimento . Mas observe que esse conjunto é indecidível para geral (caso contrário, poderíamos calcular apenas iterando de para e verificando a associação em ). Além disso, a função cresce incrivelmente rápido. É uma variante da função de castor ocupado: qual é a saída mais longa de uma máquina de Turing de comprimento descritivoJ K (n

JK(n)={w:K(w)=n}.
2n2nnnK(w)n=1|w|JK(n)
gK(n)=maxwJK(n)|w|
n? Se isso aumentasse mais lentamente do que alguma função computável, poderíamos decidir o problema da parada: dado um TM , construa que simula e imprime em cada etapa. Se o comprimento da descrição de for , então: parará no máximo etapas; ou não para.MMM1MnMgK(n)M

Agora, para a pergunta de Andrew, temos que , onde é o idioma original. Portanto, a única maneira de evitar contendo entradas muito grandes em seria se contivesse apenas seqüências de caracteres muito compactáveis. (Observe que, caso contrário, podemos ignorar completamente a distinção entre análise de pior e de caso médio aqui, porque calculamos a média de mais de strings, mas o tamanho da maior string está crescendo mais rápido do que qualquer função computável de . )IK(n)=SJK(n)SIK(n)nS2nn

Eu sinto que é provavelmente impossível construir qualquer não trivial (isto é, infinito) que contenha apenas cadeias não compactáveis, mas que seja decidível. Mas eu não sei. No entanto, espero que isso dê intuição a respeito de por que não devemos esperar que a maioria dos idiomas tenha crescendo mais lentamente que uma função computável.SfnK

Para recuar um pouco, a questão é comparar o desempenho nas entradas de comprimento com o desempenho nas entradas que podem ser compactadas no comprimento . Mas temos noções de compressão que são muito mais tratáveis ​​(e menos poderosas) que a Complexidade Kolmogorov. Uma maneira simples é fornecer um circuito de tamanho , que na entrada o número binário produz o ésimo bit de . Observe que aqui a ampliação do tamanho da entrada é no máximo exponencial (um circuito do tamanho tem no máximo entradas possíveis).nnnbbwn2n

Assim, podemos reformular a pergunta, deixando E defina analogamente. A razão da esperança aqui é que a maioria das cordas requer um circuito quase tão grande quanto a própria corda, e nenhuma corda é mais do que exponencialmente maior que o circuito necessário. Talvez neste caso nós poderíamos encontrar línguas onde e são semelhantes assintoticamente.

IC(n)={wS:the smallest circuit implicitly specifying w has size n}.
fnCfnfnC

Uma questão bem relacionada é a complexidade de linguagens implícitas como IMPLICIT_SAT é NEXP-complete, e geralmente a versão implícita dos problemas de NP-complete é NEXP-complete. Decidir IMPLICIT_SAT é pelo menos tão fácil quanto usar o circuito para escrever todos os e executar um algoritmo para SAT em . Portanto, se para SAT, isso parece quase uma evidência de que IMPLICIT_SAT no caso médio é quase tão rapidamente decidível quanto SAT no pior caso. Mas não sei como comparar diretamente sua noção com linguagens implícitas porque a noção de "menor circuito para

IMPLICIT_SAT={circuits C:C implicitly specifies w,wSAT}.
wwfnC=Θ(fn)w"não entra em jogo para idiomas implícitos.

Espero que isso seja útil / interessante!

Não tenho certeza de um livro que mencione problemas implícitos, mas aqui estão algumas notas de aula: http://people.seas.harvard.edu/~salil/cs221/spring10/lec8.pdf

usul
fonte
|JK(n)|=2n ? Mas nem toda descrição é mínima.
Andrew Andrew
1
@AndrewMacFie, à direita, deve ser "no máximo". Fixará.
usul
Obrigado por adicionar esta resposta :) Parece que para qualquer algoritmo para 3-SAT, vai crescer rapidamente. fnK
18713 Andrew Andrew
4

Um caso fácil parece ser o local em que o idioma contém apenas instâncias preenchidas. Quando é obtido de um idioma , preenchendo cada instância do tamanho com símbolos, pode estar na região de .S L n 2 n - n f K n 2 f nSSLn2nnfnK2fn

András Salamon
fonte
Observe que a resposta de Yury inclui essa e também torna preciso o "pode ​​estar na região de".
András Salamon