Complexité du test d'une valeur par rapport au calcul d'une fonction

36

En général, nous savons qu'il est plus facile de tester si une fonction prend une valeur particulière à une entrée donnée que d'évaluer la fonction à cette entrée. Par exemple:

L'évaluation du permanent d'une matrice de nombre entier non négatif est # P-difficile, mais indiquer si un tel permanent est nul ou non nul est en P (correspondance bipartite)
Il y a n nombres réels $a_1,...,a_n$ , tel que le polynôme $\prod_{i=1}^{n}(x - a_i)$ ait les propriétés suivantes (en effet, la plupart des ensembles de $n$ nombres réels auront ces propriétés). Pour une entrée donnée $x$ , tester si ce polynôme est égal à zéro prend des multiplications et des comparaisons $\Theta(\log n)$ (par le résultat de Ben-Or , car le zéro a $n$ composants), mais l’évaluation du polynôme ci-dessus prend au moins $\Omega(\sqrt{n})$ étapes, dePaterson-Stockmeyer.
Le tri nécessite $\Omega(n \log n)$ étapes sur un arbre de comparaison (également $\Omega(n \log n)$ étapes sur un arbre de décision algébrique réel, toujours d'après le résultat de Ben-Or), mais le test de sélection d'une liste à l'aide de $n-1$ comparaisons .

Existe-t-il des conditions générales sur un polynôme suffisantes pour impliquer que la complexité (algébrique) de tester si le polynôme est égal à zéro équivaut à la complexité de l'évaluation du polynôme?

Je recherche des conditions qui ne dépendent pas de la connaissance préalable de la complexité des problèmes.

( Clarification 27/10/2010 ) Pour être clair, le polynôme ne fait pas partie de l'entrée. Ce que cela signifie, c’est que, étant donné une famille fixe de fonctions $\{ f_n \}$ (une pour chaque taille d’entrée (longueur binaire ou nombre d’entrées)), je souhaite comparer la complexité du problème langage / décision $\{ X : f_n(X) = 0 \text{ where } n \text{ is the "size" of } X \}$ avec la complexité d'évaluer les fonctions . $\{f_n\}$

Précision: je m'interroge sur la complexité asymptotique de l'évaluation / test des familles de polynômes. Par exemple, sur un champ fixe (ou un anneau, tel que ), "le permanent" n’est pas un polynôme unique, mais une famille infinie où est le permanent d'une matrice sur ce champ (ou anneau). $\mathbb{Z}$ $\{perm_{n} : n \geq 0 \}$ $perm_{n}$ $n \times n$

cc.complexity-theory reference-request algebraic-complexity Joshua Grochow
la source

La réponse à votre question ne dépend-elle pas seulement du polynôme lui-même, mais également de sa représentation?

ilyaraz

@ilyaraz: Vous ne savez pas ce que vous voulez dire. Le polynôme ne fait pas partie de l'entrée.

arnab

Joshua, peux-tu 'latexatiser' la question pour une meilleure lisibilité?

Suresh Venkat

4

J'ai trouvé un article de Valiant ( dx.doi.org/10.1016/0020-0190(76)90097-1 ) "Complexité relative du contrôle et de l'évaluation", qui considère essentiellement la même question mais dans le réglage standard de la machine de Turing, plutôt que un cadre algébrique. Il ne répond pas à ma question, mais si vous trouvez cette question intéressante, vous pourriez également trouver son article intéressant.

Joshua Grochow

1

Makowski "Les utilisations algorithmiques du théorème de Feferman-Vaught" est peut-être pertinent. Il définit les polynômes en faisant la somme de structures définissables par MSOL sur des graphiques et montre qu'il est facile de les évaluer lorsque les graphiques sont liés par une largeur d'arbre

Yaroslav Bulatov

4

Sur , le test de zéro et l'évaluation sont "presque" identiques dans le sens suivant: Supposons que vous avez un arbre de décision qui teste si un polynôme irréductible est différent de zéro. Nous travaillons sur , nous ne pouvons donc tester que l’égalité mais nous n’avons pas "<". C'est la différence importante avec le deuxième exemple de la question! Maintenant , prenez le chemin typique, par exemple, le chemin emprunté par presque toutes les entrées (nous suivons toujours le « » -branch). De plus, prenez le chemin typique de tous les éléments de la variété . Soit le noeud sur lequel ces deux chemins prennent une branche différente pour la première fois. Soit $\mathbb{C}$ $f$ $\mathbb{C}$ $\not=$ $V(f)$ $v$ sont les polynômes qui sont testés le long du préfixe commun des deux chemins. Puisque est fermé, tous les éléments qui se trouvent dans et atteignent se trouvent aussi dans . Par conséquent, si , alorsun des est nulle sur . Nous appliquons Nullstellensatz de Hilbert et obtenir que $h_1,\dots,h_m$ $V(f)$ $V(f)$ $v$ $V(h_m)$ $f(x) = 0$ $h_i$ $x$ $h_1 \cdots h_m$ pour certains polynômes qui est coprime de . En bref, alors que nous necalculonspas , pour décider si , nous devons calculer pour certains coprimes . $f g = h_1 \cdots h_m$ $g$ $f$ $f$ $f(x) = 0$ $fg$ $g$

Markus Bläser
la source

Donc, la complexité du test de

est essentiellement capturée par la complexité de l’ évaluation de

. Ensuite, puisque

est irréductible, la complexité de l'évaluation de

est liée polynomialement par la complexité de l'évaluation de

, le degré de

et le nombre de variables. Donc, si

a un degré polynomial et que tester

est suffisamment facile, alors tester et évaluer sont équivalents. (Cependant, si

f (x) = 0

$f(x)=0$

f g

$fg$

f

$f$

f

$f$

f g

$fg$

f g

$fg$

f

$f$

f (x) = 0

$f(x)=0$

d e g f

$deg f$ est grand ou si le test est difficile - disons que le degré de

est très grand - alors cela en dit très peu.)

g

$g$

Joshua Grochow

Je ne comprends pas: si vous pouvez évaluer

, vous pouvez alors tester pour zéro en effectuant une seule opération supplémentaire, à savoir un test d'égalité à la fin. Ce qui pourrait mal se passer, c’est que l’évaluation de

est moins chère que celle de

pour une raison quelconque. (Remarque: évaluer

signifie évaluer à un point générique, c'est-à-dire à un temps indéterminé.)

f

$f$

f g

$fg$

f

$f$

f

$f$

Markus Bläser

Précisément. Évaluer

pourrait être plus facile que d'évaluer

. (Je sais qu'évaluer

signifie évaluer à un point générique; je ne comprends pas vraiment pourquoi vous pensiez que votre dernière remarque entre parenthèses était nécessaire, mais c'est peut-être une autre remarque.) Qu'est-ce que vous n'obtenez pas exactement? Sur la base de votre dernier commentaire, je dirais que nous comprenons tous les deux la situation et sommes d’accord avec la compréhension de chacun ... Voir aussi "La complexité des facteurs de polynômes multivariés" de Burgisser, qui donne la même conclusion que celle que j’avais énoncée dans mon précédent commentaire.

f g

$fg$

f

$f$

f

$f$

Joshua Grochow

Autre conclusion intéressante de cette discussion: bien que tester si le permanent d’une matrice non négative soit égal ou non à zéro soit facile, il est facile de vérifier si le permanent d’une matrice complexe arbitraire est égal à zéro si et seulement si l’évaluer est permanent.

Joshua Grochow

Désolé, j'ai mal compris votre premier commentaire. Tout va bien.

Markus Bläser

5

Makowski "Les utilisations algorithmiques du théorème de Feferman-Vaught" est peut-être pertinent. Il définit les polynômes en faisant la somme de structures définissables par MSOL sur des graphiques et montre qu'ils sont faciles à évaluer lorsque les graphiques sont liés par une largeur d'arbre.

Cela ne dit pas grand-chose sur la différence de complexité des tests / évaluations au-delà du FPT. Tester une valeur signifie demander s'il existe un paramètre de variables tel que la formule donnée de MSO2 sur un graphe donné ait la valeur true, alors que l'évaluation implique l'énumération des assignations trop satisfaisantes de la formule de MSO2. Cela semble être lié à la question de savoir comment la complexité du comptage SAT est liée à la complexité de SAT.

Edit 10/29 Un autre concept utile pourrait être d'examiner la propriété Uniform Difficult Point. Apparemment, les polynômes avec cette propriété sont soit faciles à évaluer en tous points, soit difficiles à évaluer presque à chaque point. Makowski donne quelques références sur les diapositives 46-52 - http://www.cs.technion.ac.il/admlogic/TR/2009/icla09-slides.pdf

Yaroslav Bulatov
la source

3

Je vais faire l’idée que l’évaluation d’un polynôme dans pour un nombre premier fixe (ou toute extension de celui-ci, et avec les coefficients limités au même corps) conviendra à votre critère. $q(x)$ $\mathbb F_p$ $p$

plus concrètement, considérons un polynôme dans . Nous savons que dans , donc si nous supposons qu'un polynôme est déjà sous forme réduite lorsqu'il est donné en entrée, nous considérons simplement l'un des éléments suivants: et en conséquence, en évaluant n'importe lequel de ces polynômes à ou prend au plus 2 opérations arithmétiques. $\mathbb F_2[x]$ $x^2=x$ $\mathbb F_2$ $0,1,x,x+1$ $0$ $1$

Je crois qu'une déclaration similaire "temps constant via un nombre fixe d'opérations arithmétiques" s'applique plus généralement à où où est premier. notez que si n'est pas corrigé, cette instruction n'est plus valide $\mathbb F_q$ $q=p^n$ $p$ $n$

Carter Tazio Schonwald
la source

1

Carter: d'après votre raisonnement, techniquement correct, il en va de même pour tout ensemble fini de polynômes. Cependant, pour considérer la complexité asymptotique de manière significative, nous devons considérer des familles infinies de polynômes. Cela implique de travailler sur des champs finis mais en laissant le champ (taille) varier, ou de travailler sur des champs infinis. Par exemple, quand on dit "le permanent" en fait , nous parlons de la famille infinie

, où

est le permanent d'un

matrice.

{p e r m_{n} : n \geq 0}

$\{perm_{n} : n \geq 0\}$

p e r m_{n}

$perm_{n}$

n \times n

$n \times n$

Joshua Grochow

1

assez juste, clarifions l’énoncé de la question avec "des polynômes dans un champ infini" plutôt qu’une tentative de réponse qui indique une clarification nécessaire :) votre exemple avec le permanent ne rend pas cela évident, parce que les matrices sont toujours fixes anneau ou champ. De plus, dans le cas de

, je ne me limite pas à ne considérer que ces 4 polynômes, mais plutôt à utiliser la relation d'équivalence de

pour réduire tout polynôme de degré supérieur à l'un de ces quatre polynômes dans le temps linéaire dans les polynômes diplôme.

F_{2}

$\mathbb F_2$

x^{2} = x

$x^2=x$

Carter Tazio Schonwald

1

Carter: Je pensais qu'il était clair que je posais des questions sur les asymptotiques, mais j'ai clarifié. Vous pouvez également utiliser des polys multivares où le nombre de vars n'est pas fixe. Désolé pour le vote négatif, mais je ne pense pas que vous méritez la moitié de la prime (+25) pour indiquer que des ensembles finis de polys à 1 var peuvent être évalués avec O (1) ops. Je sais que vous souligniez quelque chose de moins évident, mais cela n’était pas pertinent pour la question: comme il a déjà été souligné dans les commentaires sur le Q , le poly ne fait pas partie de l’entrée. Donc, sur F_2, il n'y a en effet que 4 polys à 1 var à prendre en compte (utiliser x ^ 2 = x n'est pas nécessaire).

Joshua Grochow

Hmm, votre clarification est toujours en panne, vous devez avoir un anneau fixe ou sur le terrain pour la

substance ou son non - sens.

p e r m_{n}

$perm_n$

Carter Tazio Schonwald

1

Je suis d'accord avec vous en général, j'ai donc corrigé la clarification. Fait intéressant, dans le cas de polynômes à 0,1, -1 coeff (tels que perm et det), permettre au champ de varier n’est pas un non-sens total. On pourrait imaginer un résultat tel que: "Tester si

vaut 0 est aussi difficile que d'évaluer

sur

" (pour une séquence spécifiée

de puissances premières, pas nécessairement toutes les mêmes caractéristiques ). Certes, ce ne serait pas un résultat aussi naturel que sur un champ fixe.

d e t_{n}

$det_{n}$

d e t_{n}

$det_{n}$

F_{p_{n}}

$\mathbb{F}_{p_{n}}$

p_{n}

$p_{n}$

Joshua Grochow

3

Je ne suis pas sûr de bien comprendre la question, mais laissez-moi tenter de vous éclairer.

En règle générale, l'évaluation d'un polynôme à certaines valeurs est plus facile que le test d'identité, en particulier lorsque la représentation du polynôme s'effectue via un circuit (une représentation succincte). Cependant, il existe de nombreux algorithmes de tests d'identité aléatoires ( Schwarz-Zippel étant le plus simple) qui fonctionnent uniquement avec des évaluations.

Dans certains cas particuliers, nous proposons des tests de type "boîte noire" permettant de vérifier si un polynôme est égal à zéro ou non, simplement en les évaluant selon un ensemble de points prédéfini. Un exemple simple de ceci est si le polynôme est 'clairsemé' (a seulement monômes). Pour simplifier l’exposé, supposons que le polynôme soit multilinéaire (chaque monôme est un produit de variables distinctes). $n^{O(1)}$

Un moyen naturel d'envoyer un polynôme multiligne multivarié à un univarié consiste à utiliser la substitution . Le polynôme résultant est à dire . Cela pourrait bien être un polynôme de degré exponentiel, mais passons modulo pour une petite plage de 's. Maintenant , un serait « mauvais » pour une paire de monômes si et get mappées à la même monôme modulo $x_i \mapsto y^{2^i}$ $\sum_{i\in S} \alpha_i y^{a_i}$ $y^r - 1$ $r$ $r$ $y^a$ $y^b$ $y^r - 1$ . Ou en d'autres termes, divise . Donc tant que ne divise pas , cela ne se produira pas. Par conséquent, il suffit de parcourir une plage polynomiale de . Ainsi, il suffit d'évaluer le polynôme à certaines racines d'unités et nous pouvons comprendre que le polynôme est nul ou non. $r$ $a - b$ $r$ $\prod_{i,j\in S} (a_i - a_j)$ $r$

Les algorithmes de test d'identité dans les boîtes noires ont progressé davantage. À l’heure actuelle, la plupart d’entre elles se trouvent alors à une profondeur restreinte 3 circuits (somme des produits de sommes de variables). (FWIW) Une partie de cela est mentionnée plus en détail dans les chapitres 3 et 4 de ma thèse de maîtrise . Et Saxena et Seshadri ont également fait l’objet de nouvelles améliorations récemment.

Ramprasad
la source

À moins que je manque un lien avec les tests d'identité, je pense que vous avez peut-être mal compris. Outre le fait que les polynômes ne font pas partie de la réponse à ma question - je suis plutôt intéressant dans un problème de décision et un problème de fonction défini par une famille de polynômes - je ne pose pas de question sur le test d'identité, mais tester, étant donné l'entrée

, si

. Ceci est a priori plus facile que le problème général: étant donné l'entrée

, évaluez

. Espérons que la clarification que je viens d'ajouter à la question rend cela plus clair.

x

$x$

f (x) = 0

$f(x)=0$

x

$x$

f (x)

$f(x)$

Joshua Grochow

Ah! Je vois ... Merci pour la clarification; ma réponse n'est pas trop pertinente dans ce cas.

Ramprasad

1

Tout problème #P, ou même # P / poly, peut être écrit sous forme de polynôme: créez un circuit à partir de portes NAND, écrivez-les en tant que où et valent des entiers valant 0-1, et additionnez toutes les entrées. . Cela donne un polynôme en pour les entrées de taille . Le problème de la décision est de savoir si c'est 0. $1-xy$ $x$ $y$ $\mathbb{Z}[x_1,...,x_n]$ $n$

Colin McQuillan
la source

Oui. Ceci est une version légèrement plus générale de l'exemple du permanent. Un tel problème de décision est dans

(ou

). On pense que

est significativement plus dur que

(puisqu'il est aussi dur que toute la hiérarchie polynomiale). Connaissez-vous une condition générale sur les problèmes

qui, si elle est satisfaite par une fonction

,

implique que

n’est pas plus difficile que sa version de décision?

N P

$NP$

N P / p o l y

$NP/poly$

# P

$\# P$

N P

$NP$

# P

$\# P$

# P

$\# P$

f

$f$

f

$f$

Joshua Grochow

There's a conjecture that the natural counting versions of NP-complete problems are always #P-complete, but I don't know any other relationship. A sort of trivial condition would be that the problem is self-reducible and f is bounded by a polynomial.

Colin McQuillan

Complexité du test d'une valeur par rapport au calcul d'une fonction

Réponses: