Est

J'ai pensé partager cette question car elle pourrait être intéressante pour d'autres utilisateurs ici.

Supposons qu'une fonction qui est dans une classe uniforme (comme ) se trouve également dans une petite classe non uniforme (comme , c'est-à-dire non uniforme ), cela implique-t-il que la fonction est contenue dans une classe uniforme plus petite ( comme )? Si la réponse à cette question est positive, quelle est la plus petite classe de complexité uniforme qui contient ? S'il est négatif, peut-on trouver un contre-exemple naturel intéressant? $NP$ $AC^0/poly$ $AC^0$ $P$ $NP \cap AC^0/poly$

Est-ce que contenu dans ? $AC^0/poly \cap NP$ $P$

Remarque: Un ami a déjà partiellement répondu à ma question hors ligne, j'ajouterai sa réponse s'il ne l'ajoute pas lui-même.

La question est ma deuxième tentative de formaliser la question informelle suivante:

La non-uniformité peut-elle nous aider à calculer les problèmes uniformes naturels?

En relation:

Existe-t-il un candidat pour un problème naturel en ? $P/poly−P$

cc.complexity-theory circuit-complexity uniformity Kaveh
la source

@Kaveh: Peut-être qu'une question intéressante serait de demander un problème naturel en P / poly et NP, mais pas en P. (Ou peut-être que c'est trop facile?)

Robin Kothari

@Robin: cela semble intéressant, mais je ne suis pas sûr qu'il serait plus facile de trouver un problème naturel dans .

N P \cap P / p o l y - P

$NP \cap P/poly - P$

Kaveh

@all: J'ai besoin de réfléchir un peu plus à cette question et aux réponses. Cela semble une question très naturelle. Mais je me sens mal à l'aise sur les réponses: premièrement, nous pouvons affaiblir l'hypothèse en remplaçant par où est une fonction à croissance très rapide; deuxièmement, le contre-exemple n'est pas seulement en mais a des circuits de taille 1 car la fonction est constante sur toutes les entrées de taille pour tout ! Ces deux raisons pourraient indiquer que ce n'est pas la bonne question à poser.

N E X P \neq E X P

$NEXP \neq EXP$

N T i m e (f) \neq D T i m e (f)

$NTime(f) \neq DTime(f)$

f

$f$

A C^{0} / p o l y

$AC^0/poly$

n

$n$

n

$n$

Kaveh

@Kaveh: Peut-être voudrez-vous regarder la classe YP, définie par Scott Aaronson. C'est comme P / poly, mais les "conseils" ne sont pas fiables. En d'autres termes, c'est comme NP intersection coNP, mais le témoin ne peut dépendre que de la longueur d'entrée. YP est en P / poly et est une classe uniforme. Peut-être qu'un problème dans PJ mais pas dans P est un exemple du problème que vous recherchez. Il serait naturel, uniforme, pas en P, en P / poly, et éventuellement non trivial puisque l'avis doit être vérifié par le circuit.

Robin Kothari

@Kaveh: La classe YP ("Yoda Polynomial-Time") est plus formellement définie dans l'article de Scott "L'apprenabilité des états quantiques" [quant-ph / 0608142]

Alessandro Cosentino

Réponses:

Voici une simplification de la réponse de Ryan. Supposons que . Définissez la langue . L'hypothèse se traduit par . Aussi, trivialement . $\Lambda \in NE \setminus E$ $L = \{x : |x| \in \Lambda\}$ $\Lambda \in NE \setminus E$ $L \in NP \setminus P$ $L \in AC^0/poly$

Yuval Filmus
la source

Belle réponse Yuval!

Dai Le

Essentiellement, la même transformation est utilisée dans le livre 1974 pour montrer que E ≠ NE si et seulement si NP ∖ P contient un langage de pointage.

Tsuyoshi Ito

Juste pour être sûr: ai-je bien compris que

la longueur de

écrite en unaire?

| x |

$|x|$

x

$x$

Vincent

@Vincent Ici,

est une chaîne plutôt qu'un entier, et

est sa longueur.

x

$x$

| x |

$|x|$

Yuval Filmus

oui c'est ce qui m'embrouille. Si

est la longueur d'une chaîne, alors

est un entier, alors comment peut-il être un élément de

| x |

$|x|$

| x |

$|x|$

Λ

$\Lambda$

Vincent

Réponse à votre première question: Semble peu probable.

Théorème: Si puis . $NP \cap AC^0/poly \subseteq P$ $NEXP = EXP$

Étant donné un circuit qui produit un bit, définissez la décompression de C comme étant la chaîne de bits obtenue en évaluant sur toutes les entrées possibles. Autrement dit, la décompression est . $C$ $C$ $C(0^n) C(0^{n-1}1) C(0^{n-2}10) \cdots C(1^n)$

Définissez le problème succinct 3SAT comme suit: étant donné un circuit de taille , sa décompression code-t-elle une formule booléenne satisfaisable? $C$ $n$ Succinct 3SAT est bien connu pour être complet. $NEXP$

Considérez maintenant la langue

{l'entier écrit en binaire est une instance oui de Succinct 3SAT}. $L =$ $1^n |$ $n$

est clairement dans , car vous pouvez simplement coder en dur si est dans , pour chaque . $L$ $AC^0/poly$ $1^n$ $L$ $n$

est également dans : l'entier écrit en binaire a une longueur d'environ , donc la décompression de ce circuit n'a pas une longueur supérieure à . Par conséquent, l'assignation satisfaisante a une longueur maximale de . $L$ $NP$ $n$ $\log n$ $O(n)$ $O(n)$

Mais par les mêmes observations, si , alors , car cela signifie que vous avez un algorithme de temps pour décider de chaque instance de Succinct 3SAT de longueur . $L \in P$ $NEXP=EXP$ $O(n^c)$ $\log n$

Votre deuxième question est grande ouverte (et ouverte).

Ryan Williams
la source

Pourquoi avez-vous besoin de prendre un problème complet?

Yuval Filmus

Je pensais que cela rendait l'argument plus facile à suivre.

Ryan Williams

Merci Ryan pour ta gentille réponse et l'explication. Je suppose que cela ne vous dérangerait pas si j'acceptais la réponse de Yuval bien que vous ayez été la première personne à poster.

Kaveh

A la question de Kaveh "La non-uniformité peut-elle nous aider à calculer les problèmes d'uniformes naturels?"

Je pense que la réponse est "oui", parfois. Considérons, par exemple, le problème de sous-ensemble-somme: étant donné une séquence de nombres réels positifs, décidez si certains sous-ensembles totalisent jusqu'à . Il s'agit d'un problème NP-difficile même s'il est limité à des entiers positifs (Knapsack). Mais Friedhelm Meyer auf der Heide (1984) a montré que, pour tout , le problème peut être résolu par un arbre de décision linéaire de profondeur inférieure à . Dans un tel arbre, les tests sont de la forme: est une combinaison linéaire de variables d'entrée supérieure à un certain seuil. La non-uniformité est ici importante: pour tout nous pouvons avoir un algorithme entièrement différent (arbre de décision). $n$ $1$ $n$ $n^5$ $n$

Les références:

Friedhelm Meyer auf der Heide, " Un algorithme de recherche linéaire polynomial pour le problème des sacs à dos à n dimensions ", 1984

Stasys
la source

Merci. Résultat intéressant, mais en regardant un algorithme de recherche linéaire polynomial pour le problème de sac à dos n-dimensionnel , il me semble un peu tricher. La taille du programme non uniforme est exponentielle, seule la profondeur est polynomiale, c'est comme considérer tout l'arbre de calcul d'un algorithme NP sur des entrées de taille

(c'est comme des circuits de taille exponentielle en profondeur polynomiale).

n

$n$

Kaveh

Par un argument similaire, on peut dire que tout problème est résoluble en temps constant

, car le tableau de réponses peut être exprimé par un CNF. J'aime davantage la construction de Ryan et Yuval car elle montre que bien que le problème soit compliqué dans le réglage uniforme, pour chaque taille d'entrée, il est très facile à résoudre.

2

$2$

Kaveh

Kaveh, vous avez raison: ici nous nous intéressons au temps (= profondeur), pas à l'espace (= log de la taille du réseau). Mais notez qu'un algorithme trivial pour Subset-Sum nécessiterait du temps (profondeur)

pour tester tous les sous-ensembles d'une chaîne d'entrée donnée. Aussi, je pensais que vous posiez des questions sur les candidats naturels , pas seulement pour la séparation :-)

2^{n}

$2^n$

Stasys

Bien sûr, le problème Subset-Sum a un algorithme non déterministe trivial: il suffit de deviner un sous-ensemble totalisant

. Mais nous parlons d' algorithmes déterministes . Et celle de Mayer auf der Heide est déterministe. Btw je ne suis pas non plus très enthousiasmé par son résultat. S'il l'avait montré pour la taille (pas seulement pour la profondeur = le temps), nous aurions déjà

. Pourtant, c'est l'un des résultats.

1

$1$

N P \subseteq P / p o l y

$NP\subseteq P/poly$

Stasys

@Kaveh: Mais NP lui-même est un grand OU de P. La "version temporelle" de P contre NP est: peut-on remplacer ce grand OU par un arbre de décision algébrique déterministe de profondeur polynomiale (avec P sur les feuilles)? Rappelons que la profondeur triviale de Subset-Sum est 2 ^ n (pas n). Dopkin et Lipton (1978) ont montré que la profondeur n ^ 2/2 était nécessaire, et il était largement admis que cela pouvait être amélioré à n ^ k pour tout k. Mayer auf der Heide a réfuté cette croyance: k = 5 est suffisant. Ainsi, la non-uniformité PEUT aider, si nous nous intéressons à la profondeur (temps).

Stasys