Konsekwencja PIT w stosunku do bez wydajnego algorytmu

11

Biorąc pod uwagę tak, że współczynniki są ograniczone przez , czy trzymać?p , q B p qp(x1,,xn),q(x1,,xn)Z[x1,,xn]p,qBpq

Obowiązuje tutaj lemat Schwartza-Zippela, ponieważ dotyczy on pól ogólnych i i istnieje skuteczny algorytm losowy dla tego problemu.ZQ

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

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

András Salamon
źródło
1
Jak podano i ? qpq
@RickyDemer Jak jest podawany w regularnych testach tożsamości wielomianowej?
Czy wynik Kabanets-Impagliazzo nie mówi, że NIE oczekujemy skutecznej derandomizacji?
Suresh Venkat,
1
Tak. Pomyślałem, że o tym wspomnę, ponieważ w standardowej reprezentacji różne ciągi reprezentują różne elementy.
3
@SureshVenkat: Kabanets & Impagliazzo udowodniło kilka rzeczy, w tym: 1. Jeśli PIT można zdemandomizować, albo NEXP nie ma obwodów polaryzacyjnych (boolowskich), ani stały nie ma obwodów polaryzacyjnych (arytmetycznych); 2. Jeśli stały wymaga obwodów wielobiegunowych, PIT może być „słabo” zdesandomizowany. Ponieważ wnioski z 1. są ogólnie przypuszczalne, jak również przesłanka 2., powiedziałbym przeciwnie, że wynik KI mówi, że OCZEKUJEMY skutecznej derandomizacji.
Bruno,

Odpowiedzi:

8

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!PR P PN P PB P P P = B P P E = D T I M E ( 2 O ( n ) )coRPPRPPNPPBPPP=BPPE=DTIME(2O(n))

Joshua Grochow
źródło
Tak więc zachowuje się to niezależnie od pola naziemnego (współczynniki w gdzie z pewnymi ograniczeniami współczynników)? p{2,3,5,7,}{}Qpp{2,3,5,7,}{}
Rzeczywiście, jak już wskazałeś, Schwarz-Zippel-DeMillo-Lipton stosuje się do dowolnych pól, a wszystko, czego potrzebuje, jest związane ze stopniem wielomianów (nie wielkości współczynników ani wielkości obwodu). Z bardzo małą liczbą wyjątków PIT zazwyczaj oznacza wersję ograniczoną stopniem (stopień ograniczony wielomianem w liczbie zmiennych).
Joshua Grochow
Może być głupią rzeczą. Wspomniał pan o niezależności od wielkości współczynników i wielkości obwodu. Zakładam, że rozmiar zależy od stopnia i wielkości współczynnika. Czy się mylę?
2
Rozmiar obwodu może zależeć od wielkości współczynnika, w zależności od modelu (model, w którym on zależy, jest zwykle nazywany „stałym bezobsługowym”). Rozmiar obwodu zależy tylko bardzo luźno od stopnia, w tym sensie, że rozmiar jest co najmniej log stopnia, ale tak naprawdę algorytm coRP wychodzący z SZDL jest prawie o stopień. Nie zależy to nawet od funkcji podawanych jako obwody - tylko w jakiejś formie, w której można je łatwo ocenić („czarna skrzynka”).
Joshua Grochow
Dziękuję Ci. Trochę kłopotliwe jest to, że można dokonać derandomizacji bez utraty wydajności, nawet jeśli same współczynniki mogą być konstruktywnie skomplikowane
0

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 doc=1010101010c0cjest 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).n4n
  • 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?Z[x1,,xn]

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.ZQ

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((33+3)3+x)3((22+5)3+x)2xn72n/253n/3ZB=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(logB)


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.Z[x1,,xn]

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.

Thomas Klimpel
źródło
masz na myśli ? P!=NP
Mam na myśli tylko kwestię bezpłatnej algebry, ale nie to, o czym myślisz