Conséquence de PIT sur

Étant donné telle sorte que les coefficients de p , q soient bornés par B , est-ce que p ≡ q est vrai ?$p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]$$p,q$$B$$p\equiv q$

Le lemme de Schwartz-Zippel s'applique ici car il vaut pour les champs généraux et et il existe un algorithme randomisé efficace pour ce problème.$\Bbb Z\subset\Bbb Q$

Nous prévoyons que ce problème aura une dérandomisation efficace.

Quelle est la conséquence si ce problème n'a pas de dérandomisation efficace?

Puisque PIT est en , s'il n'y a pas de dérandomisation efficace, alors P ≠ R P (et, en particulier, P ≠ N P , mais ce n'est pas si surprenant, car nous nous attendons à ce que cela soit vrai de toute façon). Cela implique également, bien sûr, que P ≠ B P P , donc tout ce qui implique P = B P P devient faux. Par exemple, il n’existe pas de générateurs de nombres pseudo-aléatoires suffisamment puissants et E = D T I M E ( 2 $\mathsf{coRP}$$\mathsf{P} \neq \mathsf{RP}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{P} \neq \mathsf{BPP}$$\mathsf{P} = \mathsf{BPP}$aurait des circuits de taille sous-exponentielle!$\mathsf{E} = \mathsf{DTIME}(2^{O(n)})$

Vous vous interrogez sur les problèmes de grande image ici. Un nombre naturel peut être canoniquement représenté en notation unaire, mais cette représentation est assez inefficace en termes d'espace. Vous pouvez également le représenter en notation binaire, qui est plus économe en espace, mais qui n'est plus canonique, car vous pouvez également utiliser la notation tenaire ou la notation décimale. Mais notez que la représentation par circuits n'est pas significativement moins efficace que la notation binaire, voir par exemple

101101 = (((1+1)*(1+1)+1)*(1+1)+1)*(1+1)*(1+1)+1

Et notez que cela (...)*(1+1)peut être remplacé par x:=(...) in x+x, vous n'avez donc même pas besoin de multiplication pour cela. Mais parce que vous avez une multiplication, vous pouvez même représenter efficacement des nombres comme 1011^101101. Notez également que vous pouvez efficacement ajouter, soustraire et multiplier des nombres dans cette représentation. Mais cette représentation n'est pas limitée aux nombres, elle fonctionne même exactement de la même manière pour les fonctions polynomiales multivariées. Et pour les polynômes, c'est même une représentation tout à fait naturelle, car les polynômes sont l'algèbre libre pour les anneaux commutatifs, et la représentation en tant que circuit peut être utilisée pour n'importe quelle algèbre libre.

Mais revenons un instant aux nombres (naturels), des nombres comme . NJ Wildberger a écrit des diatribes ultrafinitistes, comme Set Theory: devriez-vous croire? . Dans la section Mais qu'en est-il des nombres naturels? l'existence de nombres comme c est admise, car on peut évidemment les noter. Mais l'existence de presque tous les nombres naturels entre 0 et $c=10^{10^{10^{10^{10}}}}$$c$$0$$c$est refusée, car la plupart de ces nombres contiendraient plus d'informations que ce que pourrait représenter l'univers physique. La plupart des diatribes m'ont juste fait rire, mais ce point m'a fait réfléchir. Des philosophes comme Willard Van Orman Quine ont protesté contre la prétention à l'existence de possibles non concrétisés, entre autres parce que ceux-ci conduisent à des éléments désordonnés qui ne peuvent pas être considérés comme identiques à eux-mêmes et distincts les uns des autres. J'ai donc trouvé tout à fait raisonnable de m'interroger sur les présentations de nombres pour lesquelles on effectue toujours l'addition, la soustraction et la multiplication, et au moins de déterminer de manière significative si deux nombres sont distincts l'un de l'autre. La représentation du circuit y parvient ...

Retour aux polynômes et représentations de circuits d'algèbres libres. Voici quelques questions générales:

• Cette représentation d'une algèbre libre permet-elle toujours un test probabiliste d'identité efficace, ou est-ce limité aux anneaux commutatifs?
  -> Le test d'identité est souvent même indécidable: Pour , le réseau modulaire libre généré par n éléments est infini et a en fait un problème de mot indécidable (Freese, Herrmann).$n\geq 4$$n$
• Existe-t-il une algèbre libre pour laquelle des tests d'identité déterministes efficaces invalideraient toute conjecture communément admise, comme P! = NP?
  -> Oui, le test d'identité pour l'algèbre libre pour les anneaux commutatifs réguliers est NP-complet. Je ne l'ai pas remarqué depuis longtemps, voir ci-dessous ...
• Un test d'identité déterministe efficace pour (= l'algèbre libre des anneaux commutatifs) invaliderait-il des conjectures intéressantes ?$\Bbb Z[x_1,\dots,x_n]$

Je m'interroge particulièrement sur l'algèbre libre des anneaux commutatifs réguliers ici (c'est-à-dire les anneaux avec une opération inverse généralisée), car ils permettraient de représenter des nombres rationnels et des fonctions rationnelles. Notez que si nous avions utilisé cette représentation uniquement pour les nombres, alors nous aurions pu nous demander si nous pouvons tester efficacement a < bcette représentation. Cette question n'a pas de sens pour l'anneau commutatif libre, mais elle pourrait avoir un sens pour les polynômes, si nous les interprétons dans le contexte d'anneaux partiellement ordonnés libres. Mais un anneau partiellement ordonné n'est qu'une structure relationnelle au lieu d'une algèbre, c'est donc un autre type de question ...

Le lemme de Schwartz-Zippel s'applique ici car il vaut pour les champs généraux et et il existe un algorithme randomisé efficace pour ce problème.$\Bbb Z\subset\Bbb Q$

Eh bien, il est vrai que le lemme de Schwartz-Zippel s'applique ici, et qu'il existe un algorithme randomisé efficace pour ce problème, mais ces deux faits ne sont pas directement liés. Rappelons qu'il est facile de représenter efficacement des polynômes comme par un circuit. Donc, si n est la taille du circuit, alors les amplitudes des coefficients de 7 2 n / 2 , ou $((3^3+3)^3+x)^3-((2^2+5)^3+x)^2x$$n$$7^{2^{n/2}}$ sont faciles à réaliser. Cela dit,test identité polynomiale probabiliste fonctionne toujours surZ. La limite sur les coefficients est quelque chose commeB=exp(exp(n)), et vous avez juste besoin de deviner au hasard un nombre premier qui ne divise pas simultanément tous les coefficients. Ilexistesuffisamment de nombres premiers d'ordreO(logB)pour le faire de manière probabiliste efficace.$5^{3^{n/3}}$$\mathbb Z$$B=\exp(\exp(n))$$O(\log B)$

$\Bbb Z[x_1,\dots,x_n]$

D'un autre côté, je crois également que vous pouvez simplement utiliser n'importe quel générateur de nombre pseudo-aléatoire raisonnable et ainsi décider du PIT à toutes fins pratiques, si vous testez juste assez longtemps. Je crois seulement que vous ne pouvez jamais vous débarrasser du doute restant (petit infinitésimal), similaire aux ensembles de mesure zéro, qui restent ennuyeux en n'étant pas vides.