Utilisation de la complexité de Kolmogorov comme «taille» d'entrée

21

S

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

Définissons maintenant les ensembles de toutes les entrées avec la complexité de Kolmogorov , et définissons la séquence Ici est la séquence de temps de fonctionnement moyen pour , sauf lorsque la "taille" des entrées est leur complexité de Kolmogorov, pas leur longueur.n f K n = 1

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

Existe-t-il des algorithmes pour lesquels est asymptotiquement significativement différent de ? Si oui, y a-t-il des problèmes dont la complexité temporelle change lors de l'utilisation de cette autre façon d'analyser les algorithmes?f K nfnfnK

Andrew
la source
4
Grande question! Une question à laquelle je me suis souvent posé des questions - j'espère qu'elle obtiendra de bonnes réponses. (J'ai ajouté la balise paramétré-complexité b / c, vous pouvez voir cela comme la question de la complexité paramétrée de SAT, par exemple, où le paramètre est la complexité de Kolmogorov.)
Joshua Grochow
3
Les chaînes aléatoires, alias la plupart des chaînes, ont une complexité de Kolmogorov proche de leur longueur d'origine. Pour la grande majorité des entrées Vous pourriez obtenir un résultat plus intéressant si vous posiez des questions sur la profondeur de calcul au lieu de la complexité de Kolmogorov. google.com/…fn=fnK
Chad Brewbaker
2
En mélangeant dans certaines instances de PARITY dans un langage dur pour former (par exemple en préfixant chaque instance avec une bascule qui décrit de quelle langue est l'instance), alors sera plus petit que . La petite taille dépend de la densité relative. f K n f nSfnKfn
András Salamon
1
Une place est dans les notes de cours de Vadhan ici (19 février): people.seas.harvard.edu/~salil/cs221/spring10/lectures.html
usul
1
@ AndrásSalamon, oui, j'espère que je ne suis pas trop bâclé, mais je pense quedevrait être essentiellement la fonction de castor occupé. nmaxw:K(w)=n|w|
usul

Réponses:

14

Considérez la fonction de parité (ou toute autre fonction qui dépend de tous / la plupart des bits de l'entrée). Pour la fonction de parité, . Donc Par contre, f n = Θ ( n ) . f K n = Θ ( 1T(w)=Θ(|w|)

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

Notez que . Ainsi et . De même, ; ainsi "croît très rapidement". De plus, il est pas difficile de voir qu'il n'y a pas calculable limite supérieure pour .max w : K ( w ) = n | w | 2 2 Ω ( n ) f K n2 2 Ω ( n ) / 2 nK ( 2 2 2 n ) = O ( n ) f K nK(22n)=O(n)

maxw:K(w)=n|w|22Ω(n)
fnK22Ω(n)/2nK(222n)=O(n)f K nfnK222Ω(n)/2nfnK
Yury
la source
9

Compte tenu de l'intérêt suscité par cette question, j'ai pensé qu'il pourrait être utile de souligner plus explicitement la raison pour laquelle nous ne devrions pas être du tout surpris par la réponse et essayer de donner des indications pour affiner la question. Cela recueille et développe certains commentaires. Je m'excuse si c'est "évident"!

Considérons l'ensemble des chaînes de complexité de Kolmogorov : Il y a au plus telles chaînes, comme il y a descriptions de longueur . Mais notez que cet ensemble est indécidable pour général (sinon, nous pourrions calculer simplement en itérant de à et en vérifiant l'appartenance à ). De plus, la fonction grandit de façon incalculable. C'est une variante de la fonction de castor occupé: quelle est la sortie la plus longue d'une machine de Turing de longueur de descriptionn

JK(n)={w:K(w)=n}.
2n2nnnK(w)n=1|w|JK(n)
gK(n)=maxwJK(n)|w|
n? Si cela devenait plus lent que certaines fonctions calculables, nous pourrions décider du problème d'arrêt: étant donné un TM , construire qui simule et imprime un à chaque étape. Si la longueur de description de est , alors soit: s'arrête au plus étapes; ou ne s'arrête pas.MMM1MnMgK(n)M

Maintenant, à la question d'Andrew, nous avons que , où est la langue d'origine. Ainsi, la seule façon d'éviter que contienne des entrées très grandes dans serait si ne contient que des chaînes très incompressibles. (Notez que, sinon, nous pouvons complètement ignorer la distinction entre l'analyse du pire et du cas moyen ici, car nous faisons la moyenne sur au plus chaînes mais la taille de la plus grande chaîne augmente plus rapidement que toute fonction calculable de . )IK(n)=SJK(n)SIK(n)nS n2nn

Je pense qu'il est probablement impossible de construire un non trivial (c'est-à-dire infini) qui ne contienne que des chaînes non compressibles, mais qui soit décidable. Mais je ne sais pas. Cependant, j'espère que cela donne une intuition quant à la raison pour laquelle nous ne devrions pas espérer que la plupart des langues croissent plus lentement qu'une fonction calculable.f K nSfnK

Pour prendre un peu de recul, la question est de comparer les performances sur les entrées de longueur aux performances sur les entrées qui peuvent être compressées à la longueur . Mais nous avons des notions de compression qui sont beaucoup plus maniables (et moins puissantes) que la complexité de Kolmogorov. Un moyen simple est de donner un circuit de taille , qui en entrée le nombre binaire produit le ème bit de . Notez qu'ici, l'explosion de la taille d'entrée est au plus exponentielle (un circuit de taille a au plus entrées possibles).nnnbbwn2n

Nous pouvons donc reformuler la question en laissant Et définissez façon analogue. La raison d'espérer ici est que la plupart des chaînes nécessitent un circuit presque aussi grand que la chaîne elle-même, et aucune chaîne n'est plus exponentiellement plus grande que le circuit requis. Peut-être que dans ce cas, nous pourrions trouver des langages où et sont similaires asymptotiquement.

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

Une question assez étroitement liée est la complexité des langages implicites comme IMPLICIT_SAT est NEXP-complete, et généralement la version implicite des problèmes NP-complete est NEXP-complete. Décider d'IMPLICIT_SAT est au moins aussi simple que d'utiliser simplement le circuit pour écrire tout , puis exécuter un algorithme pour SAT sur . Donc, si pour SAT, cela semble proche de prouver que IMPLICIT_SAT dans le cas moyen est presque aussi rapidement décidable que SAT dans le pire des cas. Mais je ne sais pas comment on comparerait directement votre notion aux langages implicites car la notion de "plus petit circuit pour

IMPLICIT_SAT={circuits C:C implicitly specifies w,wSAT}.
wwfnC=Θ(fn)w"n'entre pas en jeu pour les langues implicites.

J'espère que c'est utile / intéressant!

Je ne suis pas sûr d'un manuel qui mentionne des problèmes implicites, mais voici quelques notes de cours: http://people.seas.harvard.edu/~salil/cs221/spring10/lec8.pdf

usul
la source
|JK(n)|=2n ? Mais toutes les descriptions ne sont pas minimes.
Andrew
1
@AndrewMacFie, à droite, devrait être "tout au plus". Réparera.
usul
Merci d'avoir ajouté cette réponse :) Il semble que pour tout algorithme pour 3-SAT, va se développer rapidement. fnK
Andrew
4

Un cas facile semble être celui où le langage ne contient que des instances remplies. Lorsque est obtenu à partir d'un langage en remplissant chaque instance de taille avec symboles, peut être de l'ordre de .S L n 2 n - n f K n 2 f nSSLn2nnfnK2fn

András Salamon
la source
Notez que la réponse de Yury subsume celle-ci, et précise également que "peut être dans la région de".
András Salamon