Quelle est la «plus petite» classe de complexité pour laquelle un

Je crois que les réponses à cette question donnent des classes telles que pour tous les polynômes , il y a un problème dans la classe qui n'a pas de circuits de taille . Cependant, je pose des questions sur la taille du circuit . $p$
$p(n)$
$\omega \hspace{.02 in}(n)$

$\big(\hspace{-0.07 in}\left\langle \hspace{-0.04 in}0^{\hspace{.02 in}0}\hspace{-0.03 in},\hspace{-0.04 in}1^{\hspace{-0.03 in}1}\hspace{-0.03 in},2^{\hspace{.02 in}2}\hspace{-0.04 in},\hspace{-0.03 in}3^1\hspace{-0.04 in},\hspace{-0.03 in}4^4\hspace{-0.03 in},\hspace{-0.03 in}5^1\hspace{-0.04 in},\hspace{-0.03 in}6^{\hspace{.03 in}6}\hspace{-0.03 in},\hspace{-0.03 in}7^1\hspace{-0.03 in},\hspace{-0.03 in}8^8\hspace{-0.03 in},\hspace{-0.03 in}9^1\hspace{-0.03 in},...\hspace{-0.05 in}\right\rangle \:$ est super linéaire mais pas . Bien qu'un tel comportement pair-impair puisse être géré par le remplissage, on peut plutôt avoir des séquences extrêmement longues de valeurs super-polynomiales entre des valeurs faibles.) $\omega \hspace{.02 in}(n)$

circuit-complexity lower-bounds Communauté
la source

Je pense que les bornes inférieures super-linéaires signifient qu'il y a une borne inférieure dans .

ω (n)

$\omega(n)$

Kaveh

Je ne pense pas que nous appelions cela une fonction super-linéaire. Pour autant que je sache, ce que les gens entendent par superlinéaire est la même manière que sublinéaire est . Avez-vous une référence pour l'utilisation de superlinéaire dans votre sens? Votre séquence est infiniment souvent superlinéaire mais elle n'est pas superlinéaire.

ω (n)

$\omega(n)$

o (n)

$o(n)$

Kaveh

Je crois que l'usage standard est que la "taille de circuit superlinéaire" signifie qu'il n'a pas de circuits de taille , c'est-à-dire infiniment souvent. Les limites inférieures «presque partout» sont beaucoup plus rares et beaucoup plus difficiles à atteindre.

O (n)

$O(n)$

Joshua Grochow

Voir le blog de Fortnow sur la question de savoir quelle est la bonne définition de la grande notation oméga.

Robin Kothari

@Kaveh: Désolé, j'aurais dû être plus précis. Je voulais dire que «le problème X n'a pas de circuits de taille linéaire» équivaut généralement à dire que «le problème X a une limite inférieure de taille de circuit super-linéaire », et je crois que ces deux signifient (et devraient signifier) ce que j'ai dit dans mes commentaires précédents. L'expression "le problème X a des circuits de taille super-linéaire" me semble étrange, parce que "avoir tel ou tel circuit" est une limite supérieure, mais "super-linéaire" est une limite inférieure ...

Joshua Grochow

Réponses:

et sont tous deux connusne pas avoir -circuits pour tout k fixe et il n'y a pasenceinteconfinement connue entre eux. Détails dans monarticle de blog. $S^p_2$ $PP$ $n^k$

Mise à jour: Comme le souligne Rickey Demer, ces résultats ne donnent pas nécessairement un langage avec une borne inférieure pour tout dans . Je pense que le est probablement le plus connu. Puisque a des ensembles complets, vous pourrez peut-être obtenir un tout mais je n'ai pas de preuve complète. $n$ $S_2^p$ $\Delta^p_3$ $PP$ $n$

Lance Fortnow
la source

Comment allez - vous de «n'avez pas n

L' circuits -SIZE » à un

limite inférieure taille du circuit?

^{k}

$^k$

ω (n)

$\omega(n)$

$\hspace{.84 in}$ Voir le haut de cette page pour une séquence qui n'a pas de limite supérieure polynôme mais ne sont pas

ω (n)

$\omega(n)$

$\hspace{.58 in}$

@ EmilJeřábek: Comment obtenez-vous cela pour tout

suffisamment grand plutôt que juste pour une infinité de

n

$n$

n

$n$

$\hspace{.08 in}$ (Cela serait nécessaire pour obtenir "la taille du circuit est

" plutôt que "la taille du circuit n'est pas

ω (n)

$\omega(n)$

O (n)

$O(n)$

$\hspace{1.12 in}$

@ EmilJeřábek: Voir ma réponse au meta.stackexchange.com/a/293100/232555 .

Vous avez raison, je me concentrais sur la première partie de la preuve qui manque sur le blog, et je ne savais pas qu'il y avait un énorme problème avec la distinction des cas. Donc, de toute façon, il y a un langage dans

qui a besoin de circuits de taille

pour tout

suffisamment grand .

Δ_{3}^{P}

$\Delta^P_3$

\geq n^{k}

$\ge n^k$

n

$n$

Emil Jeřábek

Peut obtenir une limite inférieure presque partout pour

. Pour chaque

, soit

l'ensemble de tous les circuits de taille

. Pour

, appelez l'oracle une fois pour déterminer ce que la majorité des circuits de

répondent sur la

ème entrée de longueur

, et jetez de

tous les circuits qui donnent cette réponse (cela peut être codé comme une contrainte polytime sur le prochain appel oracle). Notre fonction difficile affichera la valeur opposée sur le

P^{P P [n^{2}]}

$P^{PP[n^2]}$

n

$n$

S

$S$

n \log n

$n\log n$

i = 1, \dots, n^{2}

$i=1,\ldots,n^2$

S

$S$

i

$i$

n

$n$

S

$S$

ème entrée de longueur

.. Fin pour. Maintenant, étant donné un ae-lb pour

, pouvons-nous le soulever à

i

$i$

n

$n$

P^{P P [n^{2}]}

$P^{PP[n^2]}$

P P

$PP$

Ryan Williams

Soit dMCSP la version décisionnelle du problème de taille de circuit minimale
et laissez "[1]" indiquer "une seule requête ".
La réponse à ma question semble être ,qui en fait est telle que pour chaque k entier positif, il a un $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)}$
Borne inférieure: $\omega \hspace{-0.02 in}\big(\hspace{-0.03 in}n^k\hspace{-0.03 in}\big)$

Suivez le dernier paragraphe de la page 7 de cet article , le ce paragraphe étant un de plus que le de cet argument , et en outre "observez que c'est une tâche" co_dMCSP "de décider si une table de vérité donnée de longueur est difficile" , dans le même sens que celui utilisé dans ce paragraphe de la page 7. Les DNF circuits pour un arbitraire longueur - table de vérité ont une taille au plus $k$ $k$
$\ell$

$\ell$ , sorte dMCSP est . Par conséquent $\ell^{\hspace{.03 in}2} \cdot \operatorname{polylog}(\ell)$
$\mathbf{NP}$ . $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)} \subseteq \mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}}\hspace{-0.03 in}\right)} \subseteq \mathbf{P}^{\left(\mathbf{NP}^{\hspace{.03 in}\mathbf{NP}}\hspace{-0.03 in}\right)} = \Delta^p_3$

Je ne suis pas au courant d'aucune preuve que l' une de ces s sont égalités, et ce document donne des obstructions importantes à la possibilité d'être dMCSP -Hard sous réductions de Turing aléatoires. Les égalités suivront de dMCSP étant -Hard sous forte non-déterministe ( page 6 ) de réduction d' une requête qui ont une chaîne de conseils de taille polynomiale qui est calculable par $\subseteq$ $\mathbf{NP}$
$\mathbf{NP}$
, Mais en particulier je n'ai connaissance d'aucune preuve d'une telle dureté. $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)}$

la source