Existe-t-il x tel que K (xx) <K (x), où K est la complexité de Kolmogorov.

Soit la complexité de Kolmogorov d'une chaîne . Existe-t-il une chaîne telle que . (Ici est la concaténation de avec lui-même). Une question similaire mais différente a été posée ici , mais le contre-exemple donné dans la réponse à cette question ne fonctionne pas pour celle-ci. $K(x)$ $x$ $K(xx)<K(x)$ $xx$ $x$

cc.complexity-theory kolmogorov-complexity Sune Jakobsen
la source

Réponses:

Je ne suis pas un expert de la complexité de Kolmogorov, mais je pense qu'un tel x peut être construit pour chaque fonction de complexité K comme suit. Puisque 1, 11, 1111, 11111111,…, 1 ^{2 ⁿ} ,… est un codage d'un nombre naturel n , K (1 ^{2 ⁿ} ) ne peut pas être o (log n ). Cependant, lorsque n = 2 ^m , évidemment K (1 ^{2 ⁿ} ) = K (1 ^{2 ^{2 ^m}} ) = O (log m ) = O (log log n ). Par conséquent, la séquence K (1), K (11), K (1111), K (11111111),…, K (1 ^{2 ⁿ} ),… ne peut pas être faiblement monotone, ce qui signifie qu'il existe une chaînex sous la forme 1 ^{2 ⁿ} telle que K ( xx ) <K ( x ).

Tsuyoshi Ito
la source

@Tsuyoshi, Existe-t-il une chaîne incompressible

telle que

x

$x$

K (x x) < K (x)

$K(xx)\lt K(x)$

Mohammad Al-Turkistany,

Je pense que

et K (1 ^ {2 ^ n}) = Ω (log n) se contredisent. Il veut dire: si

alors

. Sinon, la preuve semble bonne.

K (1^{2^{2^{m}}}) = O (\log m)

$K(1^{2^{2^m}})=O(\log m)$

f (n) = o (\log n)

$f(n)=o(\log n)$

K (1^{2^{n}}) \neq O (f (n))

$K(1^{2^n})\neq O(f(n))$

Sune Jakobsen

Cela semble fonctionner. En effet, je pense que cela vous donne une séquence infinie de telles cordes. Cependant, soit je me méprend sur quelque chose, soit l'énoncé de la règle de chaîne pour la complexité de Kolmogorov qui apparaît dans wikipedia ( en.wikipedia.org/wiki/Chain_rule_for_Kolmogorov_complexity ) est alors erroné. Au début, je pensais que la définition de wikipedia pourrait ne pas s'appliquer ici, car là, vous devez être en mesure de savoir où finissent X et Y commencent, alors qu'ici cela ne semble pas être nécessaire, mais lorsque Y = X vous pouvez ajouter cela à la description dans O (1) en disant "scission au milieu".

Abel Molina

@Sune: La notation Ω (⋅) a plusieurs définitions légèrement différentes. «K (1 ^ 2 ^ n) = Ω (log n)» dans ma réponse signifie «limsup K (1 ^ 2 ^ n) / log n> 0», et cela ne contredit pas «K (1 ^ 2 ^ 2 ^ m) = O (log m). »J'ai modifié la réponse pour clarifier ce point. Voir aussi Quelle définition du taux de croissance asymptotique devons-nous enseigner?

Tsuyoshi Ito,

@turkistany et tous: Notez qu'il est toujours vrai que K (xx)> K (x) -c pour une constante, je pensais que cela devrait être souligné. Cela signifie également que nous avons besoin d'une définition très précise de l'incompressible si nous voulons étudier cette question. Je suppose que la réponse est à nouveau oui, mais je n'ai pas de preuve.

domotorp

Oui. La complexité de Kolomogorov dans la pratique dépend de votre modèle. Machine de Turing, programme Java, programme C ++, ... s'il y a une idiosyncrasie dans votre modèle qui permet que cela se produise sur un ensemble fini d'entrées ce n'est pas un problème.

La meilleure question est de savoir dans quelle mesure vous pouvez vous en sortir et que le modèle reste universel.

Chad Brewbaker
la source

Je pense qu'une meilleure question est: existe-t-il un tel x pour tous les modèles? Je ne sais pas ce qu'est un "modèle" formellement, mais il semble que la réponse de Tsuyoshis fonctionne pour tous les langages de programmation raisonnables.

Sune Jakobsen,

0

$0$

x x

$xx$

x

$x$

@Tsuyoshi:

Je n'ai pas bien compris ta preuve.

$K(s)$ $s$

$TM_{ss}$ $ss = 1111...1 = 1^{2^{n+1}}$ $TM_{s}$ $s = 1^{2^n}$

Votre preuve peut-elle être appliquée à la complexité de Kolmogorov sur les MT?

$n+1 = 2^{m}$ $TM_{ss}$ peut être "alimenté" avec une nouvelle "boucle interne" (nous ajoutons certains états mais nous pouvons supprimer de nombreux états qui, dans $TM_{s}$ sont nécessaires pour "compter" $n$ ) ... Merci!

(désolé, mais je ne sais pas comment poster ceci en tant que commentaire)

Marzio De Biasi
la source

Pour écrire un commentaire sur une publication faite par quelqu'un d'autre que vous qui ne répond pas à votre question, vous avez besoin d'au moins 50 points de réputation.

Tsuyoshi Ito