Konsekwencja PIT w stosunku do bez wydajnego algorytmu

Biorąc pod uwagę tak, że współczynniki są ograniczone przez , czy trzymać?p , q B p ≡ $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$

Obowiązuje tutaj lemat Schwartza-Zippela, ponieważ dotyczy on pól ogólnych i i istnieje skuteczny algorytm losowy dla tego problemu.$\Bbb Z\subset\Bbb Q$

Oczekujemy, że ten problem będzie miał skuteczną derandomizację.

Jakie są konsekwencje tego, że problem ten nie powoduje skutecznej derandomizacji?

Ponieważ PIT znajduje się w , jeśli nie ma skutecznego derandomizacji, to (a w szczególności , ale to nie jest to takie zaskakujące, ponieważ i tak oczekujemy, że tak będzie). Oznacza to również oczywiście, że , więc wszystko, co implikuje staje się fałszywe. Na przykład, wystarczająco silne generatory liczb pseudolosowych nie istnieją, a miałby obwody o podwykładniczej wielkości!P ≠ R P P ≠ N P P ≠ B P P P = B P P E = D T I M E ( 2 O ( n )$\mathsf{coRP}$$\mathsf{P} \neq \mathsf{RP}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{P} \neq \mathsf{BPP}$$\mathsf{P} = \mathsf{BPP}$$\mathsf{E} = \mathsf{DTIME}(2^{O(n)})$

Zastanawiasz się tutaj nad problemami z dużym obrazem. Liczba naturalna może być kanonicznie reprezentowana w notacji jednoargumentowej, ale ta reprezentacja jest dość nieefektywna przestrzennie. Możesz również przedstawić go w notacji binarnej, która zajmuje więcej miejsca, ale nie jest już kanoniczna, ponieważ możesz również użyć notacji dziesiętnej lub notacji dziesiętnej. Zauważ jednak, że reprezentacja przez obwody nie jest znacznie mniej wydajna niż notacja binarna, patrz na przykład

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

Zauważ, że (...)*(1+1)można to zastąpić x:=(...) in x+x, więc nie potrzebujesz nawet do tego mnożenia. Ale ponieważ masz mnożenie, możesz nawet skutecznie przedstawiać liczby takie jak 1011^101101. Pamiętaj również, że w tej reprezentacji możesz skutecznie dodawać, odejmować i pomnożyć liczby. Ale ta reprezentacja nie ogranicza się do liczb, działa nawet dokładnie tak samo w przypadku wielomianowych funkcji wielomianowych. W przypadku wielomianów jest to nawet całkiem naturalna reprezentacja, ponieważ wielomiany są swobodną algebrą dla pierścieni komutatywnych, a reprezentacja jako obwód może być zastosowana dla dowolnej wolnej algebry.

Wróćmy jednak na chwilę do (naturalnych) liczb, takich jak . NJ Wildberger napisał kilka ultrafinitistycznych rantów, na przykład Set Theory: Are You Believe? . W sekcji Ale co z liczbami naturalnymi? istnienie liczb takich jak jest dozwolone, ponieważ można je oczywiście zapisać. Ale istnienie prawie wszystkich liczb naturalnych od do$c=10^{10^{10^{10^{10}}}}$$c$$0$$c$jest odrzucane, ponieważ większość tych liczb zawierałaby więcej informacji, niż mogłaby być reprezentowana przez fizyczny wszechświat. Większość rantów po prostu mnie rozśmieszyła, ale ten punkt skłonił mnie do myślenia. Filozofowie tacy jak Willard Van Orman Quine protestowali przeciwko twierdzeniu o istnieniu niewykonanych możliwości, między innymi dlatego, że prowadzą one do nieuporządkowanych elementów, o których nie można w sposób znaczący powiedzieć, że są identyczne i różnią się od siebie. Uznałem więc za rozsądne zastanawianie się nad prezentacjami liczb, dla których nadal wykonuje się dodawanie, odejmowanie i mnożenie, i przynajmniej w znaczący sposób określa, czy dwie liczby różnią się od siebie. Reprezentacja obwodu osiąga to ...

Powrót do wielomianów i reprezentacji obwodów wolnych algeb. Oto kilka ogólnych pytań:

• Czy ta reprezentacja wolnej algebry zawsze pozwala na skuteczne probabilistyczne testowanie tożsamości, czy jest to ograniczone do pierścieni przemiennych?
  -> Testy tożsamości jest często nawet nierozstrzygalny: Dla The darmo modularne kraty generowane przez elementów jest nieskończona i faktycznie ma problem nierozstrzygalny słowo (Freese, Herrmann).$n\geq 4$$n$
• Czy istnieje wolna algebra, dla której skuteczne deterministyczne testowanie tożsamości unieważniłoby wszelkie powszechnie uważane przypuszczenia, takie jak P! = NP?
  -> Tak, testowanie tożsamości dla wolnej algebry dla regularnych pierścieni komutacyjnych jest zakończone NP. Nie zauważyłem tego przez długi czas, patrz poniżej ...
• Czy skuteczne testowanie tożsamości deterministycznej dla (= wolna algebra pierścieni komutacyjnych) unieważnia jakieś interesujące przypuszczenia?$\Bbb Z[x_1,\dots,x_n]$

Jestem szczególnie zastanawiać swobodnego algebry regularnych pierścieni przemiennych tutaj (tzn pierścienie z uogólnioną operacji odwrotnej), gdyż pozwalają one reprezentować liczby wymierne i racjonalne funkcji. Zauważ, że gdybyśmy użyli tej reprezentacji tylko dla liczb, moglibyśmy się zastanawiać, czy możemy skutecznie przetestować a < btę reprezentację. To pytanie nie ma sensu dla wolnego pierścienia przemiennego, ale może mieć sens dla wielomianów, jeśli interpretujemy je w kontekście wolnych częściowo uporządkowanych pierścieni. Ale częściowo uporządkowany pierścień jest tylko strukturą relacyjną zamiast algebry, więc jest to inny rodzaj pytania ...

Obowiązuje tutaj lemat Schwartza-Zippela, ponieważ dotyczy on pól ogólnych i i istnieje skuteczny algorytm losowy dla tego problemu.$\Bbb Z\subset\Bbb Q$

Cóż, to prawda, że ​​stosuje się tutaj lemat Schwartza-Zippla i że istnieje skuteczny algorytm losowy dla tego problemu, ale te dwa fakty nie są bezpośrednio powiązane. Przypomnij sobie, że łatwo jest skutecznie reprezentować wielomiany, takie jak za pomocą obwodu. Jeśli więc jest wielkością obwodu, łatwo jest osiągnąć współczynnik wielkości lub . To powiedziawszy, probabilistyczny wielomian tożsamości badania nadal pracuje nad . Ograniczenie na współczynnikach jest takie jak$((3^3+3)^3+x)^3-((2^2+5)^3+x)^2x$$n$$7^{2^{n/2}}$$5^{3^{n/3}}$$\mathbb Z$$B=\exp(\exp(n))$, po prostu musisz losowo odgadnąć liczbę pierwszą, która nie dzieli jednocześnie wszystkich współczynników. Wystarczająca liczba liczb pierwszych rzędu wystarcza do wykonania tego w efektywny sposób probabilistyczny.$O(\log B)$

Byłbym dość zaskakujący, gdyby PIT ponad mógł zostać zdesandomizowany. Ale podobna niespodzianka przydarzyła mi się wcześniej, kiedy testy pierwotności zostały zdestandalizowane.$\Bbb Z[x_1,\dots,x_n]$

Z drugiej strony uważam również, że możesz po prostu użyć dowolnego rozsądnego generatora liczb pseudolosowych i tym samym zdecydować o PIT do wszystkich praktycznych celów, jeśli tylko przetestujesz wystarczająco długo. Wierzę tylko, że nigdy nie możesz pozbyć się pozostałych (nieskończenie małych) wątpliwości, podobnych do zestawów miary zero, które pozostają denerwujące, ponieważ nie są puste.