Arguments pour / contre la conjecture de Kolmogorov sur la complexité du circuit de P

Selon un récit historique (non vérifié), Kolmogorov pensait que chaque langue dans a une complexité de circuit linéaire. (Voir la question précédente de la conjecture de Kolmogorov selon laquelle a des circuits de taille linéaire .) Notez que cela implique .$\mathsf{P}$$P$$\mathsf{P}\neq \mathsf{NP}$

La conjecture de Kolmogorov, cependant, est susceptible d'échouer. Par exemple, Ryan Williams écrit dans un article récent : "La conjecture serait surprenante, si elle est vraie. Pour les langues en nécessitant temps, il semble peu probable que la complexité de tels problèmes serait magiquement rétréci à la taille , simplement parce qu'un circuit différent peut être conçu pour chaque longueur d'entrée. "$\mathsf{P}$$n^{100^{100}}$$O(n)$

D'un autre côté, Andrey Kolmogorov (1903-1987) est largement reconnu comme l'un des principaux mathématiciens du XXe siècle. Il est assez difficile d'imaginer qu'il aurait proposé une conjecture complètement absurde. Par conséquent, pour mieux le comprendre, j'ai essayé de trouver des arguments qui pourraient réellement soutenir sa surprenante supposition. Voici ce que je pourrais imaginer:

Supposons . On peut alors choisir un langage L \ in \ mathsf {P} , tel que L ait une complexité super-linéaire à la fois dans le modèle uniforme et dans le modèle non uniforme. Il y a alors deux possibilités:$\mathsf{P}\not\subseteq \mathsf{SIZE}(lin)$$L\in \mathsf{P}$$L$

1. Il est un connu explicite algorithme (machine de Turing) qui accepte $L$ . À partir de cela, nous pouvons construire une famille de fonctions explicite qui doit avoir une complexité de circuit superlinéaire. Cependant, cela peut être considéré comme improbable, car personne n'a été en mesure de trouver un tel exemple en plus de 60 ans d'intenses recherches sur les circuits.

2. On ne connaît pas explicitement algorithme pour $L$ . Par exemple, son existence est prouvée par des moyens non constructifs, comme l'Axiom of Choice. Ou, même si l'algorithme explicite existe, personne n'a pu le trouver. Étant donné, cependant, qu'il existe une infinité de langages qui peuvent jouer le rôle de $L$ , il est encore peu probable qu'ils se comportent tous de cette manière peu amicale.

Mais alors, si nous rejetons les deux options comme improbables, la seule possibilité qui reste est qu'un tel $L$ n'existe pas. Cela signifie $\mathsf{P}\subseteq \mathsf{SIZE}(lin)$ , qui est précisément la conjecture de Kolmogorov.

Question: Pouvez-vous penser à un autre argument pour / contre la conjecture de Kolmogorov?

La note de bas de page de mon article que vous citez fait également référence à un "argument" heuristique, du moins ce que nous pensons être l'intuition de Kolmogorov - la résolution positive du treizième problème de Hilbert.

http://en.wikipedia.org/wiki/Hilbert's_thirenth_problem

En particulier, Kolmogorov et Arnold ont prouvé que toute fonction continue sur variables peut être exprimée comme une composition de "simples": addition de deux variables et fonctions continues sur une variable. Par conséquent, sur la "base" des fonctions continues à une variable et de l'addition à deux variables, chaque fonction continue sur variables a une "complexité de circuit" .O ( n 2 ) n O ( n 2$n$$O(n^2)$$n$$O(n^2)$

Il semble que Kolmogorov croyait qu'il existe un analogue discret, où "continu dans variables" devient "booléen dans variables et poly temps calculable", et où la "base" donnée ci-dessus devient des fonctions booléennes à deux variables.n ( n $n$$n$$(n)$

La réponse de Stasys à la question précédente fournit une intuition potentiellement en faveur: /cstheory//a/22048/8243 . Je vais essayer de reformuler ici si je comprends bien. L'intuition clé est de voir un circuit comme, non pas un algorithme, mais un encodage d'un ensemble (l'ensemble qu'il accepte). Nous pouvons obtenir une limite supérieure sur la taille de l'encodage par le temps d'exécution de l'algorithme (c'est-à-dire traduire un time- TM en un circuit de taille- ), mais on ne sait pas quelle relation inverse devrait exister. Si une langue est dans , cela implique peut-être que l'appartenance est suffisamment "locale" pour être encodée de manière très concise.t $t$$t$$\mathsf{P}$

Autrement dit, l'appartenance à est une déclaration sur le temps d'exécution d'un algorithme alors que les circuits linéaires sont (peut-être) une déclaration sur la taille de codage des ensembles de mots de longueur fixe. Les deux sont des déclarations sur la simplicité de la langue mais ils vivent dans des mondes peut-être très différents.$\mathsf{P}$

Une autre intuition mentionnée par Stasys vient de la "chaîne indicatrice" d'une langue, qui formalisons comme la chaîne infinie où le bit est si la ème chaîne lexicographique est dans la langue et est sinon. Un TM (polytime) pour la langue est un oracle (rapide) pour la chaîne --- donné en binaire, produit le ème bit. Un circuit (de taille linéaire) pour les entrées de longueur est un oracle (concis) pour le préfixe longueur- de la chaîne. La conjecture devient "toute chaîne infinie qui a un oracle" rapide "a des oracles de préfixe" concis "."1 j 0 j j n 2 $j$$1$$j$$0$$j$$j$$n$$2^n$

Rien de ce qui précède n'explique pourquoi et" linear "pourraient être les bons paramètres respectifs pour l'énoncé; mais je pense qu'ils montrent qu'une intuition naturelle - que les circuits agissent comme des algorithmes, et que des algorithmes plus compliqués nécessitent circuits tout aussi complexes - peuvent être trompeurs.$``\mathsf{P}"$