Limites inférieures du circuit et complexité de Kolmogorov

Considérez le raisonnement suivant:

Soit la complexité de Kolmogorov de la chaîne . Le théorème d'incomplétude de Chaitin dit que $K(x)$ $x$

pour tout cohérent et système formel suffisamment solide , il existe une constante (ne dépendant que du système formel et sa langue) de telle sorte que pour toutes les chaînes , ne peut pas prouver que . $S$ $T$ $x$ $S$ $K(x) \geq T$

Soit une fonction booléenne sur variables st la complexité de Kolmogorov de son spectre est au plus . Soit la complexité du circuit de , c'est-à-dire la taille du circuit minimal calculant . $f_n$ $n$ $k$ $S(f_n)$ $f_n$ $f_n$

Une limite supérieure (approximative) pour est pour une constante et est une fonction de castor occupée (le maximum d'étapes possibles est l'arrêt) Turing machine avec une description de la taille peut effectuer). (Pour chaque du spectre, construisez le minterm de l'affectation de vérité correspondante et prenez OU de tous ces minterms ensemble.) $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$

Supposons maintenant pour une famille infinie de fonctions booléennes , nous avons une preuve formelle que nécessite des circuits de taille , c'est-à-dire $L = \{f_n\}_{n}$ $L$

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

$S \vdash \forall n \geq n_0, \ g(n)\cdot n \leq S(f_n)$ où .

g (n) \in ω (1)

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

Si nous prenons pour être suffisamment grand, nous aurons $n$

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

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

En particulier, cela serait une preuve que la complexité de Kolmogorov du spectre de est au moins , ce qui est impossible. $f_n$ $T$

Cela conduit à deux questions:

1) Il devrait y avoir quelque chose de mal dans le raisonnement ci-dessus. Principalement parce que cela rendrait les bornes inférieures du circuit superlinéaire formellement non prouvables.

2) Connaissez-vous des approches similaires pour montrer les barrières pour les limites inférieures, c'est-à-dire montrer que certains types de limites inférieures (de circuit) ne sont pas formellement prouvables?

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

des idées intéressantes. quelque peu lié à la preuve razborov / rudich concernant les «preuves naturelles» qui esquisse les obstacles à P =? NP (mais aussi probablement applicable à d'autres séparations de classes de complexité énumérées à titre d'exemples dans l'article) .. avez-vous lu cet article? voir aussi barrières P =? NP et barrières / complexité du circuit monotone . il semble que la structure des séparations de classes de complexité est similaire à celle des preuves non probables.

vzn

pouvez-vous élaborer sur le "spectre" de f_n? existe-t-il un moyen de formuler la question sans se référer au "spectre"?

vzn

il est probablement vrai que l'on peut étudier la complexité des fonctions en étudiant la plus petite TM [au sens de table / états d'états] qui les calcule et que cela correspondra grossièrement aux bornes inférieures du circuit. si vous pouvez montrer qu'il est impossible, plutôt que vraiment difficile, de trouver la plus petite MT, vous pourriez avoir quelque chose là-bas. cependant, il est "simple" de trouver la plus petite MT via une énumération canonique des circuits ou des MT. si vous vous demandez pourquoi cette approche fonctionne, il pourrait être utile de comprendre pourquoi la question ne pose pas de problème.

vzn

Droite. Merci pour les références. Je connais le papier Natural Proofs. Je ne sais pas si la question peut être formulée sans "spectre". Ce que je veux dire par "spectre" est la séquence

(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 Find

Réponses:

Il n'y a rien de mal à votre argument, mais il n'y a pas de contradiction. Vous prouvez que de certains assez grand la complexité de Kolmogorov du spectre de est toujours au moins . Mais cette affirmation est trivialement vraie! Bien que nous ne puissions pas prouver que la complexité de Kolmogorov d'une chaîne est grande, si nous avons une séquence, alors à un certain point elle ne doit contenir que des chaînes de grande complexité. Alors, quel est ce que vous avez? Il doit satisfaire , ce qui est un nombre que nous ne pouvons pas calculer (à cause de ), donc il n'y a aucun problème du tout. $N$ $f_n$ $T$ $N$ $N>g^{-1}(c \cdot BB(T))$ $BB$

domotorp
la source

Merci. Je suis tombé dans le piège de croire que l'on pouvait "choisir" une valeur de N suffisamment grande, mais comme vous le faites remarquer, ce n'est pas possible dans , et comme vous le faites également remarquer correctement, cela serait en fait vrai pour toute famille de séquences croissantes.

S

$S$

Magnus Find

Voici une situation problématique encore plus simple. Soit la première chaîne (dans l'ordre lexicographique) telle que ; une telle chaîne existe pour tous les . Alors . $A(k)$ $K(A(k)) \geq k$ $k$ $K(A(k)) \geq k$

Le coupable pourrait être que le système formel ne peut pas calculer . $BB(T)$

Edit: Voici une situation problématique "plus explicite". Soit la longueur maximale d'une chaîne dont la complexité de Kolmogorov est au plus ; existe prouvablement. Alors . $\alpha(k)$ $k$ $\alpha(k)$ $K(0^{\alpha(k)+1}) > k$

Yuval Filmus
la source

Pourquoi cette situation est-elle problématique? Vous n'avez pas donné de programme dont la sortie serait A (k) et sa longueur serait inférieure à k.

domotorp

J'ai la même confusion que Domotor, mais je conviens qu'un problème avec le raisonnement d'OP est qu'un système formel ne sera pas en mesure de prouver les limites supérieures sur pour assez grand .

B B (k)

$BB(k)$

k

$k$

Sasho Nikolov

C'est problématique (sans doute) dans le même sens que la question d'origine.

Yuval Filmus

Je ne comprends toujours pas. Vous ne présentez pas une chaîne et une preuve que sa complexité Kolmogorov est grande. Vous présentez une preuve qu'il existe une chaîne dont la complexité est grande.

Sasho Nikolov

Je pense qu'ils sont problématiques de différentes manières. En le lisant, vous pointez une affirmation vraie et précise, qui n'a pas de preuve. Comme je l'expose dans ma question, je souligne que cela implique une preuve de quelque chose qui n'est pas prouvable.

Magnus Find