Conjecture de Kolmogorov selon laquelle a des circuits de taille linéaire

Dans son livre, Boolean Function Complexity, Stasys Jukna mentionne (page 564) que Kolmogorov croyait que chaque langue en P avait des circuits de taille linéaire. Aucune référence n'est mentionnée et je n'ai rien trouvé en ligne. Quelqu'un en sait-il plus là-dessus?

cc.complexity-theory reference-request circuit-complexity ho.history-overview Hamid
la source

Paging @Stasys :)

Suresh Venkat

référez-vous également à ceci ici rjlipton.wordpress.com/2009/02/12/is-np-too-big-or-p-too-small

T ....

Cette "conjecture" de Kolmogorov n'est qu'une rumeur. Il n'a bien sûr été publié nulle part. Dans l'ex-URSS, "publier" les mathématiques signifiait quelque chose de différent: faire un exposé dans un séminaire, ou le dire à vos collègues au déjeuner, ou autre. Le comptage des papiers n'était pas un problème. Donc, je ne peux pas exclure que cette "conjecture" ait été juste racontée à Levin par Kolmogorov lors de leur marche vers un séminaire à la MGU (Université de Moscou). (En fait, j'ai également recommandé cette façon de faire les mathématiques.) Alors, ne prenez pas cela trop au sérieux - tout comme une "rumeur" qui (inutile de le dire) n'a pas été réfutée au fil des ans ...

Stasys

P \subseteq s i z e (n^{k}) \Rightarrow P \neq N P

$\mathsf{P} \subseteq \mathsf{size}(n^k) \Rightarrow \mathsf{P} \neq \mathsf{NP}$

k

$k$

. Ce dernier est renforcé à

par le théorème de Kannan.

\forall k \in N : Σ_{4}^{P} ⊈ s i z e (n^{k})

$\forall k \in \mathbb{N}: \Sigma_4^{\mathsf{P}} \not \subseteq \mathsf{size}(n^k)$

Σ_{2}^{P}

$\Sigma_2^{\mathsf{P}}$

Sasho Nikolov

@Stasys, vous devez publier cela comme une réponse pour que la question reçoive une réponse (afin que le site ne continue pas à remonter à la première page).

Kaveh

Réponses:

[Suite à une suggestion de Kaveh, je mets mon commentaire (quelque peu étendu) comme réponse]

Cette "conjecture" de Kolmogorov n'est qu'une rumeur. Il n'a été publié nulle part. Dans l'ex-URSS, «publier» les mathématiques signifiait quelque chose de différent de ce qu'il fait aujourd'hui: donner une conférence lors d'un séminaire ou le dire à vos collègues au déjeuner. Le comptage des papiers n'était pas un problème. (En fait, j'ai également recommandé cette façon de faire les mathématiques.) Je ne peux pas exclure la possibilité que cette "conjecture" ait été juste racontée à Levin par Kolmogorov lors de leur marche vers un séminaire à l'Université de Moscou. Ne prenez donc pas cela trop au sérieux comme une conjecture formelle; c'est juste une rumeur qui (inutile de le dire) n'a pas été réfutée au fil des ans. Mais comme un géant comme Kolmogorov a sérieusement réfléchi à ce problème et n'a pas exclu la possibilité d'un "pouvoir du diable", la conjecture devrait être traitée assez sérieusement,

Voici une spéculation (très, très grossière) de ma compréhension de cette conjecture. Notre intuition (apparemment erronée) sur le fonctionnement des circuits repose sur la visualisation du calcul par un programme comme un processus séquentiel qui recueille progressivement des informations sur la chaîne d'entrée. Cette intuition est empruntée à notre vision du fonctionnement d'une machine de Turing. Mais chaque chaîne d'entrée détermine un sous-circuit (témoin ou ). Et pour qu'un circuit soit correct, il suffit que les ensembles de sous-circuits pour et $x$ $f(x)=1$ $f(x)=0$ $f^{-1}(1)$ sont disjoints. C'est-à-dire qu'un circuit est un "codage local" compact d'une partition donnée du cube. La longueur de ce code est la complexité de Kolmogorov de la chaîne binaire donnée de longueur . Unalgorithme detemps polynomial, cependant, fait plus: il donneun"codage global" de la chaîne infinie entière pour tout . Maintenant, une chaîne infinie permettant un encodage de taille $f^{-1}(0)$ $n$ $f_n$ $2^n$ $f$ $n$ $f$ $n^c$ doit être "simple", et ses préfixes "devraient" permettre des encodages "locaux" encore plus compacts. Bien sûr, il reste un mystère pourquoi Kolmogorov pensait que des encodages "locaux" même de taille pour certains pourraient alors suffire ... $cn$ $c$

PS Désolé, j'ai oublié d'ajouter: Une excellente confirmation de ma "thèse" selon laquelle les circuits doivent être considérés comme des codes (statiques) plutôt que des algorithmes (dynamiques) est le célèbre théorème de David Barrington selon lequel toute la classe peut être simulée par polynôme -size programmes de branchement de largeur 5. La vue "collecte d'informations" ici est totalement fausse: on ne sait même pas comment calculer la fonction majoritaire en ne gardant que 5 bits d'informations. Une idée intelligente de David était juste de coder $NC^1$ le comportement d'une formule donnée par des séquences particulières de 5 permutations, et pour montrer que les chaînes acceptées et rejetées obtiendront des codes différents. Le fait est qu'un programme de branchement ne "calcule" pas non plus - il code plutôt les chaînes d'entrée par ses sous-programmes: quand une entrée arrive, les bords incohérents disparaissent, et nous avons un code de cette entrée.

Stasys
la source

Existe-t-il des exemples non triviaux de langues qui prennent en charge cette conjecture?

Igor Shinkar

@Igor: Je ne sais pas. Quelques indications (faibles) sont mentionnées ici . En fait, j'ai tendance à la réponse de GMB: très probablement, la conjecture a été stimulée par leur solution du problème du 13e Hilbert, et non par des considérations combinatoires.

Stasys

Je suis loin d'être aussi bien informé sur ce sujet que Stasys, mais j'ai entendu une justification différente de cette conjecture que je pourrais aussi bien partager.

J'ai entendu que la conjecture était basée sur la solution positive au treizième problème de Hilbert, qui a été résolue conjointement par Komolgorov et son élève Arnold. Le théorème (qui est beaucoup plus général que le problème énoncé par Hilbert) dit:

Chaque fonction continue d'un nombre fini de variables peut être exprimée par la composition finie de fonctions à variable unique, ainsi que par un nombre fini d'applications de l'opérateur binaire . $+$

On me dit que, sur la base de certains détails de mise en œuvre de la preuve de ce théorème, cela peut être considéré comme un analogue continu de l'affirmation selon laquelle . $\exists k \, \, \, P \subset SIZE(n^k)$

Désolé, je ne suis pas qualifié pour être plus précis que cela - si quelqu'un d'autre a entendu cette idée, il pourrait peut-être m'aider.

GMB
la source

pouvez-vous donner une référence pour ce thm plz

vzn

@GMB: bien observé - cela pourrait être une explication encore plus précise de la raison de cette conjecture.

Stasys