Czy Merlin może przekonać Artura o określonej kwocie?

11

Merlin, który ma nieograniczone zasoby obliczeniowe, chce przekonać Arturowi, że

m|pN., p głównypk
dla (N.,m,k) przy k=O(logN.) i m=O(N.). Obliczenie tej sumy w prosty sposób (potęgowanie modułowe i dodawanie) wymaga czasu N.(loglogN.)2)+o(1) z pomnożeniem opartym na FFT. * Ale Arthur może wykonywać tylkooperacjeO(N.).

(Notacja, dla zgodności z wcześniejszymi wersjami tego pytania: Niech suma będzie równa mα ; wówczas pytanie brzmi, czy α jest liczbą całkowitą.)

Czy Merlin może przekonać Artura sznurkiem o długości O(N.) ? Jeśli nie, to czy uda mu się przekonać Artura interaktywnym dowodem (całkowita komunikacja oczywiście musi być O(N.) )? Jeśli tak, to czy Merlin mógłby zastosować ciąg o długości o(N.) ? Czy Arthur mógłby wykorzystać czas o(N.) ?

Artur nie ma dostępu do niedeterminizmu ani innych specjalnych narzędzi (metod kwantowych, wyroczni innych niż Merlin itp.), Ale w razie potrzeby ma przestrzeń O(N.) . Oczywiście, Artur nie musi obliczać sumy bezpośrednio, wystarczy jedynie przekonać, że dane potrójne (N, m, k) sprawiają, że równanie jest prawdziwe lub fałszywe.

Należy zauważyć, że z k=0 nie jest możliwy do obliczania sumy w czasie O(N.1/2)+ε) stosując Lagarias-Odlyzko metody. Dla k>0 suma jest superliniowa i dlatego nie można jej zapisać bezpośrednio (bez np. Redukcji modułowej), ale nie jest jasne, czy istnieje szybki algorytm.

Byłbym także zainteresowany dowolnym algorytmem do obliczania sumy (modułowej lub innej) innej niż bezpośrednie zasilanie i dodawanie.

* liczby do obliczenia, czas lg k log N ( log log N ) 1 + o ( 1 ) = log N ( log log N ) 2 + o ( 1 ) dla każdego obliczenia.N./logN.lgklogN.(loglogN.)1+o(1)=logN.(loglogN.)2)+o(1)

Charles
źródło
1
Podobne post Math.SE .
Hsien-Chih Chang 之 之
1
Tak, powiązane. Kluczową różnicą jest to, że pytanie matematyczne SE zakłada, że ​​Merlin ma zero zasobów obliczeniowych, a to zakłada, że ​​ma nieograniczone zasoby.
Charles
3
Co z czasem potrzebnym na testowanie pierwotności?
Peter Shor
1
@Charles: Nie widzę tego Skalowanie N do zliczania liczb pierwszych. Czy potrafisz to wykorzystać? Myślałbym, że to wymaga skalowania superliniowego. Sito Eratostenesa dajealgorytmO(N2). NO(N2)
Joe Fitzsimons
1
Algorytm wynika z Lagarias i Odlyzko. Jest opisany np. Dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf (I nie jest to ale ˜ O (O(N.))O~(N.).
Charles

Odpowiedzi:

7

Piszę to osobno od mojego wcześniejszego specjalnego przypadku, ponieważ uważam, że jest to inne podejście do problemu i ma niewielki związek z moją drugą odpowiedzią. To może nie być dokładnie to, czego szukasz, ale jest proste i zbliża się.

Istnieje dowód, który Arthur zawsze zaakceptuje, jeśli dowód jest poprawny, ale zostanie odrzucony z prawdopodobieństwem . Oto jak to działa: Merlin wysyła Arthur para(pI,ci=p k i  mod m)dla każdego głównegopN. Artur weryfikuje sumę (biorąc czasO(N/log(N))×O(log(N))=O(N)1(loglogN.)2)+o(1)(pja,doja=pjak mod m)pN.O(N./log(N.))×O(log(N.))=O(N.)). Arthur sprawdza, czy odpowiednia liczba bodźców zostało zapewnione (przez obliczenia ), która jest sublinear w N . Wreszcie dla losowych par S N potwierdza, że p jest liczbą pierwszą i że p k ic i  mod  m . Wymaga to czasu S N O ( ( log log N ) 2 + o ( 1 ) ) . Biorąc S = ( log log N )π(N.)N.S.N.ppjakdoja mod mS.N. O((loglogN.)2)+o(1)) , otrzymujemy liniowe skalowanie czasu. W ten sposób ułamekSwszystkich par jest weryfikowany. Jeśli któryś z nich zawiedzie, Arthur oczywiście odrzuci. Aby Arthur zaakceptował niepoprawny dowód, musi istnieć co najmniej jedna para, która nie przejdzie jednego z tych dwóch testów (lub liczba par musi być mniejsza niżπ(N),co zostało wcześniej sprawdzone). Stąd jako frakcjaSwszystkich par są kontrolowane, test nie powiedzie się do niewłaściwej dowodu z prawdopodobieństwa co najmniejS.S.=(loglogN.)-(2)+o(1))S.π(N.)S.S.

Zauważ, że dla dużych jest to znacznie lepsze niż losowe zgadywanie, które kończy się prawdopodobieństwem 1N. .1m=1O(N.)

Joe Fitzsimons
źródło
Jeśli opublikowanie dwóch odpowiedzi jest złą praktyką, daj mi znać, a ja je scalę. Zostawiłem je osobno, ponieważ ten ostatni właśnie do mnie przyszedł i jest zupełnie innym ujęciem w porównaniu do pierwszej odpowiedzi.
Joe Fitzsimons
1
nie mam nic przeciwko. szczególnie w pytaniach CW często występuje wiele odpowiedzi.
Suresh Venkat
@Suresh: Tak, wiem, ale to nie jest CW i nie chcę być dziwką.
Joe Fitzsimons
2
Bardzo miła odpowiedź. Maksymalizuje oba zasoby - ciąg Merlina wynosi a Artur używa Θ ( N ) czasu. Nitpick: indywidualne sprawdzenie liczb pierwszych zajmie zbyt dużo czasu, ale Arthur może je wszystkie wygenerować i porównać z listą Merlina (wymagając, aby była w porządku). Θ(N.)Θ(N.)
Charles
1
@JoeFitzsimons: w porządku :). jeśli obie odpowiedzi zasługują na powtórzenie, otrzymasz podwójne punkty :)
Suresh Venkat
6

To pełna odpowiedź na problem, który w ogóle nie korzysta z Merlina.

Deléglise-Dusart-Roblot [1] uzyskując algorytm, który określa liczbę bodźce się dla , które są przystające do l modulo K , w czasie O ( x 2 / 3 / log 2 x ) . Modyfikacja algorytmu Lagarias-Odlyzko [2] sposób ta sama być obliczona w czasie O ( x 1 / 2 + O ( 1 ) ) .xlk,O(x2)/3)/log2)x).O(x1/2)+o(1)).

Korzystając z dowolnego algorytmu, znajdź liczbę liczb pierwszych we wszystkich klasach liczb pierwszych mod mod, aż ich iloczyn będzie większy niż Dla każdego głównego Q , ma całkowitą liczbę liczb pierwszych w każdej reszcie razy klasy tej klasy pozostałości w k -tej potęgi; daje to wartość p N p liczba  pierwsza p km.q,k

p głównypN.pk(modq).

Skorzystaj z chińskiego twierdzenia o pozostałej wartości, aby określić wartość sumy mod 2)3)logm.

Przez liczby pierwsze twierdzenie największym prime potrzebne jest więc daje to sumę w czasie O ( N 1 / 2 + o, ( 1 ) ) .(1+o(1))logm,O(N.1/2)+o(1)).

Bibliografia

[1] Marc Deléglise, Pierre Dusart i Xavier-François Roblot, Liczenie liczb pierwszych w klasach pozostałości , Mathematics of Computation 73 : 247 (2004), s. 1565-1575. doi 10.1.1.100.779

π(x)

[3] Charles, odpowiedź na MathOverflow . (Tak, to ta sama osoba. Zobacz inne odpowiedzi tam dla różnych podejść.)

Charles
źródło
5

kk=xϕ(m)x

ϕ(m)mN.pxϕ(m)0 mod mp|mpxϕ(m)1 mod mk=xϕ(m)pN.,p prjammipkπ(N.)-y mod mymπ(N.)N.

1<N.<mmα1<π(N.)<m

Joe Fitzsimons
źródło