Eine NP-vollständige Variante des Factorings.

Aroras und Baraks Buch beschreibt Factoring als folgendes Problem:

$\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$

Weiter in Kapitel 2 fügen sie hinzu, dass das Entfernen der Tatsache, dass Primzahl ist, dieses Problem NP-vollständig macht, obwohl dies nicht mit der Schwierigkeit verbunden ist, Zahlen zu faktorisieren. Es sieht so aus, als könnte es eine Reduzierung von SUBSETSUM geben, aber ich habe es nicht gefunden. Hast du hier mehr Glück? $p$

EDIT 1. März: Die Prämie ist für -completeness Nachweis unter Verwendung von determinis Karp (oder Cook) Reduktion. $NP$

cc.complexity-theory np-hardness factoring Michaël Cadilhac
quelle

@turkistany: FWIW, ich betrachte es als schlechten Stil, NP kursiv zu schreiben, und als schlechten Stil und schlechten LaTeX, um es in den Mathematikmodus zu setzen (da der Abstand zwischen den Buchstaben unterschiedlich ist).

Michaël Cadilhac

@ Michaël, Entschuldigung, kehrte zum ursprünglichen Stil zurück. Ihre Frage hat mich aufgeregt :)

Mohammad Al-Turkistany

Eine etwas vollständigere Beschreibung: Auf Seite 63 des Buches schreiben sie: Alon und Kilian (in persönlicher Mitteilung) haben gezeigt, dass in der Definition der Sprache Factoring in Beispiel 2.3 die Bedingung, dass der Faktor p Primzahl ist, notwendig ist, um das zu erfassen Factoring-Problem, da diese Sprache ohne diese Bedingung NP-vollständig ist (aus Gründen, die nichts mit der Härte von Factoring-Ganzzahlen zu tun haben).

MS Dousti

Natürlich habe ich nach einer Arbeit von Alon und Kilian gesucht, die "Factoring" und "NP-complete" enthält. Ich habe keine gefunden (ich denke, das ist in gewissem Sinne auch natürlich). :(

Tsuyoshi Ito

@Michael Ich rendere eigentlich gerne Klassen als

anstatt als NP. Nein ?

N P

$\mathsf{NP}$

Suresh Venkat

Antworten:

Dies ist keine richtige Antwort, aber es ist nah. Das Folgende ist ein Beweis dafür, dass das Problem bei randomisierten Reduktionen NP-schwer ist.

Es gibt eine offensichtliche Beziehung zur Teilmengensumme: Angenommen, Sie kennen die Faktoren von : , , , . Nun wollen Sie eine Teilmenge von so dass $N$ $p_1$ $p_2$ $\ldots$ $p_k$ $S$ $p_1$ $\ldots$ $p_k$

\log L \leq \sum_{p_{i} \in S} \log p_{i} \leq \log U .

$\displaystyle \log L \leq \sum_{p_i \in S} \log p_i \leq \log U.$

Das Problem beim Versuch, diese Idee zu verwenden, um das Problem zu zeigen, ist NP-schwer: Wenn Sie ein Teilmengenproblem mit den Zahlen , , , , können Sie nicht notwendigerweise Primzahlen in einer Polynomzeit wie z das (wobei mit meine ich ungefähr proportional zu). Dies ist ein echtes Problem, weil Sie, da die Teilmengen-Summe nicht stark NP-vollständig ist, diese für große ganze Zahlen . $t_1$ $t_2$ $\ldots$ $t_k$ $\log p_i \propto t_i$ $\propto$ $\log p_i$ $t_i$

Angenommen, wir fordern, dass alle Ganzzahlen in einem Teilmengen-Summenproblem zwischen und und dass die Summe ungefähr $t_1$ $\ldots$ $t_k$ $x$ $x(1+1/k)$ . Das Teilmengen-Summenproblem ist immer noch NP-vollständig, und jede Lösung ist die Summe vonganzen Zahlen. Wir können das Problem von ganzen Zahlen in reelle Zahlen umwandeln, wenn wir zwischenund $\frac{1}{2}\sum_i t_i$ $k/2$ $t'_i$ $t_i$ , und anstatt dass die Summe genau, muss sie zwischenund $t_i+\frac{1}{10k}$ $s$ $s$ . Wir müssen unsere Zahlen nur miteiner Genauigkeit vonetwamehrangeben, umdies zu tun. Wenn wir also mit Zahlen mitBits beginnen und reelle Zahlenmiteiner Genauigkeitvon ungefährBitsangeben können, können wir unsere Reduktion durchführen. $s + \frac{1}{10}$ $4 \log k$ $B$ $\log p_i$ $B + 4 \log k$

$T$ $T+ T^{5/8}$ $\theta(T^{5/8}/\log T)$

$t_i$ $B$ $T_i$ $3B$ $p_i$ $T_i$ $9/8B$ $T_i$ $\log T_i \propto t_i$ $9/8\, B$ $p_i \approx T_i$ $\log p_i \propto t_i$ $9/8\,B$ $N=\Pi_i p_i$ $L$ $U$

Peter Shor
quelle

Ich verstehe die Reduzierung nicht. Damit das Teilmengen-Summenproblem NP-vollständig ist, muss die Zahl binär angegeben werden. Wenn wir Ganzzahlen wollen, deren Logarithmen in einer Instanz des Teilmengen-Summenproblems nahe an den Zahlen liegen, brauchen wir exponentiell viele Ziffern. Wie überwinden Sie das?

Tsuyoshi Ito

p_{n + 1} - p_{n} = O (\log^{2} n)

$p_{n+1} - p_n = O(\log^2 n)$

p_{n}

$p_n$

T

$T$

α = 0.525

$\alpha = 0.525$

c_{1} = \infty

$c_1 = \infty$

c_{2} = 1

$c_2 = 1$

Bin gerade darauf gestoßen. Ich sollte beachten, dass ich nicht weiß, was der ursprüngliche Kilian-Alon-Beweis war. Mein einziges Wissen über den Beweis stammt aus einer Kommunikation mit Noga, die sich nicht an die Details des ursprünglichen Beweises erinnerte, und der Beweis, den er rekonstruierte, war genau dieser. Es ist zu beachten, dass dies auch als deterministische Reduktion unter einigen starken zahlentheoretischen Annahmen beschrieben werden kann (z. B. dass es in jedem Intervall der Form [x, x + Polylog (x)] eine Primzahl gibt).

Boaz Barak

Ich habe gerade mit Joe Kilian gesprochen. Er sagte, dass der Beweis, den er und Alon erbracht hätten, zufällige Null-Fehler-Reduktionen beinhaltete. Soweit ihm bekannt ist, ist die deterministische Reduktion noch offen, es sei denn, Sie gehen von einer zahlentheoretischen Annahme aus, wie Boaz Barak bereits sagte.

Timothy Chow

$NP = PCP[O(\log{n}), O(1)]$

Ein Auszug aus einer Madhu-Zeitung :

$A$ $A$ $N, L, U$ $L \leq U \leq N$ $A$ $N$ $L$ $U$ $N$ $L$ $U$

... weit über meine komplexitätstheoretischen Fähigkeiten hinaus :-)

Marzio De Biasi
quelle

Dies ist nur eine andere Formulierung, dass dieses Problem NP-vollständig ist.

Marc Bury

{⟨ L, U, N ⟩ | (\exists p \in {L, \dots, U}) [p | N]}

$\{\langle L, U, N \rangle \;|\; (\exists p \in \{L, \ldots, U\})[p | N]\}$

Das SHORT PROOFS-Problem im Papier ist fast dasselbe wie das Problem des begrenzten Anhaltens. Eine Reduktion aus dem SHORT PROOFS-Problem wäre höchstwahrscheinlich so chaotisch wie der typische Beweis der NP-Vollständigkeit von SAT, und daher ist es unwahrscheinlich, dass der Beweis der NP-Vollständigkeit dieses Faktorfindungsproblems durch Kilian eine Reduktion aus dem konstruiert KURZBEWEISE Problem direkt.

Tsuyoshi Ito

Dies ist eine informelle, effiziente, deterministische Reduktionsidee (die möglicherweise unvollständig ist):

$\{\langle L, U, M \rangle \;|\; (\exists \text{ a positive integer } p \in \{L, \ldots, U\})[p | M]\}$

$M$ $M=N_j * F_i$

Mohammad Al-Turkistany
quelle