Kann Merlin Arthur von einer bestimmten Summe überzeugen?

11

Merlin, der über unbegrenzte Rechenressourcen verfügt, möchte Arthur davon überzeugen, dass

m|pN, p primepk
für (N,m,k) mit k=O(logN) und m=O(N). Die einfache Berechnung dieser Summe (modulare Exponentiation und Addition) benötigt Zeit N(loglogN)2+o(1) mit FFT-basierter Multiplikation. * Arthur kann jedoch nurO(N)-Operationen ausführen.

(Notation zur Kompatibilität mit früheren Versionen dieser Frage: Lassen Sie die Summe gleich mα ; dann ist die Frage, ob α eine ganze Zahl ist.)

Kann Merlin Arthur mit einer Schnur der Länge überzeugen O(N)? Wenn nicht, kann er Arthur mit einem interaktiven Beweis überzeugen (die totale Kommunikation muss natürlich O(N) )? Wenn ja, könnte Merlin eine Zeichenfolge mit der Länge o(N) ? Könnte Arthur o(N) Zeit verwenden?

Arthur hat keinen Zugang zu Nichtdeterminismus oder anderen Spezialwerkzeugen (Quantenmethoden, Orakel außer Merlin usw.), hat aber bei Bedarf O(N) -Raum. Natürlich muss Arthur die Summe nicht direkt berechnen, er muss lediglich davon überzeugt sein, dass ein gegebenes Tripel (N, m, k) die Gleichung wahr oder falsch macht.

Beachten Sie, dass mit k=0 ist es möglich , die Summe der Zeit zu berechnen , O(N1/2+ε) unter Verwendung der Lagarias Odlyzko- Methode. Für k>0 die Summe superlinear und kann daher nicht direkt gespeichert werden (ohne z. B. modulare Reduktion), es ist jedoch nicht klar, ob ein schneller Algorithmus existiert.

Ich würde mich auch für einen Algorithmus interessieren, mit dem die Summe (modular oder anderweitig) berechnet werden kann, außer durch direkte Stromversorgung und Addition.

* zu berechnende Zahlen, Zeit lg k log N ( log log N ) 1 + o ( 1 ) = log N ( log log N ) 2 + o ( 1 ) für jede Berechnung.N/logNlgklogN(loglogN)1+o(1)=logN(loglogN)2+o(1)

Charles
quelle
1
Verwandte Post auf Math.SE .
Hsien-Chih Chang 21 之
1
Ja, verwandt. Der Hauptunterschied besteht darin, dass die math.SE-Frage davon ausgeht, dass Merlin keine Rechenressourcen hat, und dass diese davon ausgeht, dass er unbegrenzte Ressourcen hat.
Charles
3
Was ist mit der Zeit, die für Primalitätstests benötigt wird?
Peter Shor
1
@ Charles: Ich sehe das nicht Skalierung zum Zählen von Primzahlen. Kannst du es erklären? Ich hätte gedacht, dass es eine superlineare Skalierung erfordert. Das Sieb des Eratosthenes ergibt einenO(N2)-Algorithmus. NO(N2)
Joe Fitzsimons
1
Der Algorithmus stammt von Lagarias & Odlyzko. Es wird z. B. dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf beschrieben (und es ist nicht aber ˜ O (O(N))O~(N).
Charles

Antworten:

7

Ich poste dies getrennt von meinem früheren Sonderfall, weil ich glaube, dass es eine andere Herangehensweise an das Problem ist und wenig mit meiner anderen Antwort zu tun hat. Es ist vielleicht nicht genau das, wonach Sie suchen, aber es ist einfach und kommt näher.

Es gibt einen Beweis, den Arthur immer akzeptiert, wenn der Beweis korrekt ist, der jedoch mit Wahrscheinlichkeit abgelehnt wird1(loglogN)2+o(1)(pi,ci=pik mod m)pNO(N/log(N))×O(log(N))=O(N)π(N)NSNppikci mod mSN O((loglogN)2+o(1))S=(loglogN)(2+o(1))Sπ(N)SS

N1m=1O(N)

Joe Fitzsimons
quelle
Wenn das Posten von zwei Antworten eine schlechte Praxis ist, lassen Sie es mich wissen und ich werde sie zusammenführen. Ich habe sie getrennt gelassen, da letztere gerade zu mir gekommen sind und eine völlig andere Einstellung haben als die erste Antwort.
Joe Fitzsimons
1
für mich in Ordnung. Besonders bei CW-Fragen ist es üblich, mehrere Antworten zu haben.
Suresh Venkat
@Suresh: Ja, ich weiß, aber das ist nicht CW, und ich möchte nicht als Repräsentantenhure rüberkommen.
Joe Fitzsimons
2
Θ(N)Θ(N)
1
@ JoeFitzsimons: Es ist in Ordnung :). Wenn beide Antworten eine Wiederholung verdienen, erhalten Sie doppelte Punkte :)
Suresh Venkat
6

Dies ist eine vollständige Antwort auf das Problem, bei dem Merlin überhaupt nicht verwendet wird.

xlk,O(x2/3/log2x).O(x1/2+o(1)).

m.q,k

p primepNpk(modq).

23logm.

(1+o(1))logm,O(N1/2+o(1)).

Verweise

[1] Marc Deléglise, Pierre Dusart und Xavier-François Roblot, Zählen von Primzahlen in Restklassen , Mathematics of Computation 73 : 247 (2004), S. 1565-1575. doi 10.1.1.100.779

π(x)

[3] Charles, antworte auf MathOverflow . (Ja, dies ist dieselbe Person. In den anderen Antworten finden Sie unterschiedliche Ansätze.)

Charles
quelle
5

kk=xϕ(m)x

ϕ(m)mNpxϕ(m)0 mod mp|mpxϕ(m)1 mod mk=xϕ(m)pN,p primepkπ(N)y mod mymπ(N)N

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

Joe Fitzsimons
quelle