Théorème d'Adleman sur des demi-tours infinis?

13

Adleman a montré en 1978 que BPPP/poly : si une fonction booléenne f de n variables peut être calculée par un circuit booléen probabiliste de taille M , alors f peut également être calculé par un circuit booléen déterministe de taille polynôme en M et n ; en fait, de taille O(nM) .

Question générale: sur quels autres semirings (autres que booléens) BPPP/poly tient-il?

Pour être un peu plus précis, un circuit probabiliste sur un semi-câblage ( S , + , , 0 , 1 ) utilise ses opérations "d'addition" ( + ) et de "multiplication" ( ) comme portes. Les entrées sont des variables d'entrée x 1 , ... , x n et , éventuellement , un certain nombre de variables aléatoires supplémentaires, qui prennent les valeurs 0 et 1 , indépendamment , avec une probabilité 1 / 2 ; iciC(S,+,,0,1)(+)()x1,,xn011/2 et 1 sont respectivement les identités additive et multiplicative du semirage. Un tel circuit C calculeune fonction donnée f : S n01C si pour tout x S n , P r [ C ( x ) = f ( x ) ] 2 / trois . f:SnSxSnPr[C(x)=f(x)]2/3

La fonction de vote de m variables est une fonction partielle dont la valeur est y si l'élément y apparaît supérieur à m / 2Maj(y1,,ym)myym/2 fois parmi les et n'est pas défini , si un tel élément y n'existe pas. Une simple application des limites de Chernoff et de l'union donne les résultats suivants.y1,,ymy

Truc de la majorité: Si un circuit probabiliste calcule une fonction f : S nS sur un ensemble fini X S n , alors il y a m = O ( log | X | ) réalisations C 1 , , C m de C telles que f ( x ) = M a j ( C 1 ( x ) , Cf:SnSXSnm=O(log|X|)C1,,CmC est vrai pour tout x X . f(x)=Maj(C1(x),,Cm(x))xX

Au cours du semi-booléen, la fonction de vote est la fonction majoritaire et a de petits circuits (même monotones). Ainsi, le théorème d'Adleman suit en prenant X = { 0 , 1 } n . MajX={0,1}n

Mais qu'en est-il des autres semirings (surtout, infinis)? Qu'en est-il de la semi- arithmétique (avec addition et multiplication habituelles)?(N,+,,0,1)

Question 1: Est-ce que emprise sur le semi - anneau arithmétique? BPPP/poly

Bien que je parie pour "oui", je ne peux pas le montrer.

Remarque: Je connais cet article où les auteurs réclament sur le champ réel ( R , + , , 0 , 1 ) . Ils traitent des circuits arithmétiques non monotones et arrivent également (dans le théorème 4) à des circuits avec la fonction de vote M a j comme porte de sortie. Mais comment simuler ce M a j -gate par un circuit arithmétique (monotone ou non)? C'est-à-dire comment obtenir leur corollaire 3?BPPP/poly(R,+,,0,1)MajMaj

En fait, l'argument simple suivant qui m'a été dit par Sergey Gashkov (de l'Université de Moscou) semble montrer que cela est impossible (au moins pour les circuits capables de calculer uniquement des polynômes ). Supposons que nous pouvons exprimer comme un polynôme f ( x , y , z ) = a x + b y + c z + h ( x , y , z ) . Alors f (Maj(x,y,z)f(x,y,z)=ax+by+cz+h(x,y,z) implique c = 0 , f ( x , y , x ) = x implique b = 0 et f ( x , y , y ) = y implique a = 0 . Cela tient parce que, sur des champs de caractéristique nulle, l'égalité des fonctions polynomiales signifie l'égalité des coefficients. Notez que dans la question 1, la gamme de circuits probabilistes, et donc le domaine du Mf(x,x,z)=xc=0f(x,y,x)=xb=0f(x,y,y)=ya=0 -gate estinfini. J'ai donc l'impression que l'article lié ne traite que des circuits arithmétiques calculant les fonctions f : R nY avec de petites plages finies Y , comme Y = { 0 , 1 } . Alors M a j : Y mY est en effet facile à calculer par un circuit arithmétique. Et si Y = R ? Majf:RnYYY={0,1}Maj:YmYY=R


Correction [6.03.2017]: Pascal Koiran (l'un des auteurs de cet article) m'a fait remarquer que leur modèle est plus puissant que les circuits arithmétiques: ils autorisent les Sign-gates (sortie ou 1 selon que l'entrée est négative de ne pas). Ainsi, la fonction de vote Maj peut être simulée dans ce modèle, et je reprends ma "confusion".01


In the context of dynamic programming, especially interesting is the same question for tropical min-plus and max-plus semirings (N{+},min,+,+,0) and (N{},max,+,,0).

Question 2: Does BPPP/poly hold over tropical semirings?

Held BPPP/poly in these two semirings, this would mean that randomness cannot speed-up so-called "pure" dynamic programming algorithms! These algorithms only use Min/Max and Sum operations in their recursions; Bellman-Ford, Floyd-Warshall, Held-Karp, and many other prominent DP algorithms are pure.

Jusqu'à présent, je ne peux répondre à la question 2 (affirmativement) que dans le scénario d'erreur unilatérale , lorsque nous avons en outre besoin de sur le semiring min-plus (minimisation), ou P r [ C ( x ) > f ( x ) ] = 0Pr[C(x)<f(x)]=0Pr[C(x)>f(x)]=0sur le semiring max-plus (maximisation). Autrement dit, nous exigeons maintenant que le circuit tropical randomisé ne puisse jamais produire mieux que la valeur optimale; il peut cependant se tromper en donnant des valeurs pires qu'optimales. Mes questions relèvent cependant du scénario d' erreur bilatéral .


PS [ajouté le 27.02.2017]: Voici ma tentative de répondre à la question 1 (affirmativement). L'idée est de combiner une version la plus simple de la "Nullstellensatz combinatoire" avec une estimation du problème de Zarankiewicz pour les hypergraps n-partites, due à Erdos et Spencer. Modulo ce dernier résultat, tout l'argument est élémentaire.

Notez que la question 2 reste ouverte: la "Nullstellensatz naïve" (du moins sous la forme que j'ai utilisée) ne tient pas dans les demi-semelles tropicales.

Stasys
la source
nit: BPP est une classe uniforme définie à l'aide de PTM et non de circuits.
Kaveh
@Kaveh: oui, en ce sens, le résultat d'Adleman est encore un peu plus fort, il vaut même pour BPP / poly.
Stasys
Je ne vois pas comment l'argument simple montre l'impossibilité ... il semble montrer que les coefficients des monômes x, y et z doivent être nuls ... que me manque-t-il? De plus, si un polynôme ne peut pas calculer Maj, comment pouvez-vous représenter un calcul sur un semirage? (Quoi d'autre qu'un polynôme sur le semiring?) Intuitivement, sur un domaine infini, chaque contrainte sur certains y (imposant que sur> m / 2 y vous devez sortir y) semble "indépendante" des autres (aucun sous-ensemble de contraintes n'implique un autre) il semble donc qu'aucun polynôme "fini" ne puisse satisfaire les infiniment de contraintes indépendantes.
Ryan Williams
@Ryan: oui, cela ne montre que f = Maj implique h = Maj. Mais h a un degré> 1, donc h (x, x, z) = x est impossible. Et vous avez raison: les circuits sur demi-tours ne peuvent rien calculer d'autre que des polynômes. Donc, ils ne peuvent pas calculer le Maj. Mais les auteurs de cet article traitent des circuits {+, x, -, /}, toutes les opérations sur le terrain étant autorisées. Peut-être alors Maj peut-il encore être en quelque sorte calculé? (Je ne vois cependant pas comment.) Btw au lieu d'essayer de simuler Maj lui-même, on pourrait répondre à Q1 & Q2 en montrant qu'un Maj-gate ne peut pas diminuer considérablement la taille du circuit (ce qui est tout à fait plausible).
Stasys
@Ryan: PS Igor Sergeev a observé que Maj "pourrait" être probablement calculable sur (R, +, x, -, /). Par exemple Maj (x, y, z) est calculable par f (x, y, z) = (xy + xz-2yz) / (2x-yz) pour toutes les entrées avec | {x, y, z} | = 2. Notez que l'argument simple ci-dessus implique que, déjà sur de telles entrées, cela ne peut pas être fait (R, +, x, -). Ainsi, la division peut aider. Mais nous sommes confrontés à la division par 0 question ...
Stasys

Réponses:

3

Ce n'est qu'une réponse partielle à votre question générale (je ne suis pas sûr de ce que serait une formulation entièrement générale), mais cela suggère que travailler sur des demi-tours infinis suffisamment agréables tout en contraignant le caractère aléatoire à un domaine fini pourrait en fait banaliser la question de savoir si Le théorème d'Adleman tient.

Cfx variables. Then it turns out that already for some fixed r, C(x,r)=f(x). The reason is that for each r, the set of x with C(x,r)=f(x) determines a Zariski-closed subset of Cn, and so must be all of Cn, or else a subset of measure zero. If all of these sets were to have measure zero, then, because there are only finitely many r's in consideration, the set of x where r:C(x,r)=f(x) would also have measure zero. On the other hand, the assumption that C computes f implies this that set must be all of Cn, so it cannot have measure zero.

Andrew Morgan
la source
Interesting. More generally, a probabilistic circuit of size M is some random variable C taking its values in the set of all circuits (of that type) with at most M gates. [B.t.w. that paper of Cucker at al. allows C be arbitrarily distributed. The "majority trick" stil works.] Can I conclude from your argument that, if the range of C is finite, then Adleman's theorem is trivial when Zarinski-closed subsets are either trivial (sets themselves) or have zero measure? Have we this - "all or nothing" - effect in tropical semirings? (I am mainly interested in them.)
Stasys
I don't know how or whether the argument would generalize to other semirings, sorry. One main thing that's missing (for me) is the geometric intuition akin to how "polynomials that disagree" translates to "measure-zero subsets of Cn". For tropical semirings in particular, the operations seem so different from ordinary polynomials that it's hard to even guess at what the appropriate adaptation ought to be.
Andrew Morgan