Ist das Schreiben einer Zahl als zwei Quadrate und das Schreiben der Faktoren einer Zahl gleich schwierig?

Sei $L_1$ und wie folgt: $L_2$

$L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\}$

$L_2=\{(N,M): M<N, \exists 1<d\leq M \text{ such that d|N} \}$

Anspruch $L_1 \leq_P L_2$

Skizzenbeweis

Wenn ich wissen will, ob . $r\in L_1$

Die Anzahl der ganzzahligen Lösungen für ist gegeben durch $x^2+y^2=r$

$g(r)=\sum_{d|r}{\chi{(d)}}$ wobei $\chi (x)=sin(\frac{\pi x}{2})=\cases{ 1\text{ when }x\cong 1 \text{ mod }4 \\ -1 \text{ when }x\cong 3 \text{ mod }4 \\ 0 \text{ when } 2|x }$

Dann ist . Die Antwort lautet also " ?" ist höchstens so schwer zu beantworten wie "Was sind die Teiler von ?" $L_1=\{r: g(r)\neq 0\}$ $r\in L_1$ $r$

$\square$

Was ich gerne wissen würde ist, ob dies umgekehrt wahr ist. Stimmt es, dass ich, wenn ich eine Maschine hätte, die mir in konstanter Zeit sagen könnte, ob , eine Maschine erstellen könnte, die antworten könnte: "ist ?" in Polynomzeit? $r\in L_1$ $(M,N)\in L_2$

Motivationen

Diese Frage entstand aus einer Diskussion über diese Frage .

Entschuldigung Ich bin wirklich nur ein math.se-Mitglied, das sich verlaufen hat und zu cs.se übergegangen ist. Lassen Sie mich wissen, ob meine Frage klar ist und den Standards dieser Website entspricht. Gerne nehme ich Korrekturen vor.

complexity-theory time-complexity np decision-problem Mason
quelle

ich richtig?

\leq_{P}

$\leq_P$

Mason

Ihre Reduktion ist korrekt, aber Ihre Schlussfolgerung, dass "so hart wie" ist, ist falsch. Sie zeigen nur , dass ist höchstens so hart wie . Insbesondere zeigen Sie tatsächlich, dass höchstens so schwer ist wie ein sehr eingeschränkter Fall von , was sehr einfach sein kann.

L_{1} \leq_{p} L_{2}

$L_1\le_p L_2$

L_{1}

$L_1$

L_{2}

$L_2$

L_{1}

$L_1$

L_{2}

$L_2$

L_{1}

$L_1$

L_{2}

$L_2$

Shaull

Anstatt "einen Kreis zu befriedigen", könnte ein besserer Begriff "eine Summe von zwei Quadraten" sein.

Yuval Filmus

@Shaull, ich habe eine Sprache geändert, um Ihren Kommentar wiederzugeben.

Mason

Es ist bekannt, dass das Berechnen von bis zu einer randomisierten Polynomzeitverkürzung so schwierig wie das Faktorisieren ist. Siehe Bach, Miller und Shallit: Summen von Teilern, perfekten Zahlen und Factoring .

\sum_{d ∣ n} d

$\sum_{d\mid n}d$

Emil Jeřábek

Antworten:

Hier ist die Situation, soweit ich das beurteilen kann:

Der effizienteste bekannte Weg, um die Mitgliedschaft in zu testen, ist der Faktor . Es scheint kein effizienterer Algorithmus bekannt zu sein. $L_1$ $r$

Es gibt jedoch keine offensichtliche Reduktion, um zu beweisen . Mit anderen Worten, wenn wir eine Maschine hätten, um zu entscheiden , gibt es keine einfache Möglichkeit, diese zur Faktorisierung zu verwenden. Wenn wir eine Zahl Faktor wollen , können wir ob prüfen , aber das gibt uns nur ein Bit an Information über die Faktoren von . Das Testen von Vielfachen von (dh ob für eine ganze Zahl ) liefert keine zusätzlichen Informationen, da das Wissen, ob ausreicht, um vorherzusagen, ob für alle $L_2 \le_P L_1$ $L_1$ $N$ $N \in L_1$ $N$ $N$ $cN \in L_1$ $c$ $N \in L_1$ $cN \in L_1$ $c>0$ . Das Testen anderer Zahlen scheint auch nicht offensichtlich zu helfen. (Das Testen, ob für eine andere Zahl scheint, scheint keine nützlichen Informationen zu liefern, wenn ; und ob wir eine Möglichkeit hatten, eine andere Zahl zu finden so dass , wir wissen bereits, wie man faktorisiert, aber natürlich wissen wir nicht, wie man das macht - daher ist es unwahrscheinlich, dass eine Zahl, die wir generieren können, uns etwas Nützliches gibt Informationen zu den Faktoren von ) Dies ist kein Beweis; es ist nur handgewellte Intuition. $N' \in L_1$ $N'$ $\gcd(N,N') =1$ $N'$ $\gcd(N,N')\ne 1$ $N$

Es erscheint also plausibel, dass einfacher als , und es erscheint auch plausibel, dass sie dieselbe Schwierigkeit haben könnten. Weitere Ergebnisse zu diesem Thema sind mir nicht bekannt. $L_1$ $L_2$

DW
quelle