Preuve que les bornes supérieures du circuit pour

18

Dans la description officielle du problème de Clay pour P versus NP, il est indiqué que découlerait de la démonstration que "chaque langue de [la classe de langues reconnaissable en temps exponentiel avec une machine de Turing déterministe] peut être calculée par une famille de circuits booléens. tel que pour au moins un , ait moins de portes que le maximum nécessaire pour calculer une fonction booléenne $P \neq NP$ $E$ $<B_n>$ $n$ $B_n$ $f: \{0,1\}^n \longrightarrow \{0,1\}$ "Cependant, la seule référence est que ceci" est une observation intrigante de V. Kabanets. "Est-ce que quelqu'un pourrait me montrer une version publiée de cette implication avec la preuve?

cc.complexity-theory circuit-complexity David
la source

25

Je ne pense pas que le document de l'autre réponse contienne une réponse à votre question. En effet, je ne suis pas vraiment sûr qu'une preuve ait été publiée, car le résultat découle d'autres résultats bien connus.

La preuve de la déclaration que vous souhaitez est la suivante:

contient une fonction de complexité de circuit maximale possible sur chaque longueur d'entrée, en définissant simplement une fonction qui se révèle (en utilisant l'alternance) être différente de toutes les fonctions avec une complexité de circuit non maximale. C'est standard et l'idée de preuve peut être trouvée dans des sources comme Arora et le manuel de Barak. $\Sigma_3 E$
Si alors , par foulardage et l'effondrement de la hiérarchie polynomiale à . $P = NP$ $\Sigma_3 E = E$ $P$
Par conséquent, si il existe alors un langage en avec une complexité de circuit maximale. C'est la contradiction de ce que vous voulez prouver. $P = NP$ $E$

Ryan Williams
la source

Bien, j'ai deviné que tu serais le premier à y répondre.

Mohammad Al-Turkistany,

4

Il y a aussi une réponse dans le journal de Kabanets et Cai. Dans le théorème 10, ils prouvent que si

est dans

, alors

contient une famille de fonctions booléennes de complexité de circuit maximale. Si

, alors

et

, donc alors, par le théorème,

contient en effet un langage d'une complexité maximale.

M C S P

$MCSP$

P

$P$

E^{N P}

$E^{NP}$

P = N P

$P=NP$

M C S P \in P

$MCSP\in P$

E^{N P} = E

$E^{NP}=E$

E

$E$

Andras Farago

1

bon point, Andras! L'un des quantificateurs de la partie

peut être considéré comme résolvant MCSP.

Σ_{3} E

$\Sigma_3 E$

Ryan Williams

6

googler autour de moi m'a trouvé cet article qui a été publié avec la réfraction ci-dessous.

Problème de minimisation de circuit

Valentine Kabanets et Jin-Yi Cai

Nous étudions la complexité du problème de minimisation des circuits: étant donné la table de vérité d'une fonction booléenne f et un paramètre s, décider si f peut être réalisé par un circuit booléen de taille au plus s. Nous discutons de la raison pour laquelle il est peu probable que ce problème soit en P (ou même en P / poly) en donnant un certain nombre de conséquences surprenantes d'une telle hypothèse. Nous soutenons également que prouver que ce problème est NP-complet (s'il est vrai) impliquerait de prouver des limites inférieures de circuit fortes pour la classe E, ce qui semble dépasser les techniques actuellement connues.

Cela semble être publié ci-dessous.

résumé détaillé dans Actes du trente-deuxième Symposium annuel ACM sur la théorie de l'informatique (STOC'00), pages 73-79, 2000. rapport technique, dans Electronic Colloquium on Computational Complexity TR99-045, 1999. http: // www. cs.sfu.ca/~kabanets/Research/circuit.html
résumé étendu dans Actes du trente-deuxième Symposium annuel ACM sur la théorie de l'informatique (STOC'00), pages 73-79, 2000. http://eccc.hpi-web.de/report/1999/045/

Joshua Herman
la source

Notez que cette réponse ne répond pas à la question ci-dessus mais qu'elle fournit la référence à l'origine de cette question.

Joshua Herman

Preuve que les bornes supérieures du circuit pour

Réponses: