Varian anjak lengkap NP.

Buku Arora dan Barak menyajikan anjak piutang sebagai masalah berikut:

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

Mereka menambahkan, lebih lanjut dalam Bab 2, bahwa menghilangkan fakta bahwa adalah prima membuat masalah ini NP-lengkap, meskipun ini tidak terkait dengan kesulitan nomor anjak. Tampaknya ada pengurangan dari SUBSETSUM, tapi saya buntu menemukannya. Adakah keberuntungan yang lebih baik di sekitar sini? $p$

EDIT 1 Mar: karunia adalah untuk -completeness bukti menggunakan deterministik pengurangan Karp (atau Masak). $NP$

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

@turkistany: FWIW, saya menganggap gaya buruk untuk meletakkan NP dalam huruf miring, dan sebagai gaya buruk dan buruk LaTeX untuk memasukkannya ke mode matematika (karena jarak antar huruf berbeda).

Michaël Cadilhac

@ Michaël, Maaf, kembali ke gaya aslinya. Saya senang dengan pertanyaan Anda :)

Mohammad Al-Turkistany

Deskripsi yang agak lebih lengkap: Pada halaman 63 buku ini, mereka menulis: Alon dan Kilian (dalam komunikasi pribadi) menunjukkan bahwa dalam definisi bahasa Anjak di Contoh 2.3, syarat bahwa faktor p adalah prima diperlukan untuk menangkap masalah anjak, karena tanpa kondisi ini bahasa ini adalah NP-lengkap (karena alasan tidak ada hubungannya dengan kekerasan bilangan anjak).

MS Dousti

Secara alami, saya mencari kertas karya Alon dan Kilian yang berisi "factoring" dan "NP-complete." Saya tidak menemukannya (saya kira ini juga wajar dalam beberapa hal). :(

Tsuyoshi Ito

@ Michael Aku benar-benar seperti render kelas sebagai

daripada NP. Tidak ?

N P

$\mathsf{NP}$

Suresh Venkat

Jawaban:

Ini bukan jawaban yang cukup, tetapi sudah dekat. Berikut ini adalah bukti bahwa masalahnya adalah NP-hard di bawah pengurangan acak.

Ada hubungan yang jelas dengan jumlah subset yaitu: seandainya Anda tahu faktor-faktor : , , , . Sekarang, Anda ingin mencari subset dari sehingga $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.$

Masalah dengan mencoba menggunakan ide ini untuk menunjukkan masalahnya adalah NP-hard adalah bahwa jika Anda memiliki masalah subset-sum dengan angka , , , , Anda tidak dapat selalu menemukan bilangan prima dalam waktu polinomial seperti bahwa (dimana dengan , maksud saya kira-kira sebanding dengan). Ini adalah masalah nyata karena, karena subset-sum tidak sangat lengkap NP, Anda perlu menemukan untuk bilangan bulat besar . $t_1$ $t_2$ $\ldots$ $t_k$ $\log p_i \propto t_i$ $\propto$ $\log p_i$ $t_i$

$t_1$ $\ldots$ $t_k$ $x$ $x(1+1/k)$ $\frac{1}{2}\sum_i t_i$ $k/2$ $t'_i$ $t_i$ $t_i+\frac{1}{10k}$ $s$ $s$ $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
sumber

Saya tidak mengerti pengurangannya. Untuk masalah jumlah subset menjadi NP-complete, angka harus diberikan dalam biner. Jika kita menginginkan bilangan bulat yang logaritmanya dekat dengan angka dalam contoh masalah jumlah himpunan bagian, kita perlu banyak digit secara eksponensial. Bagaimana Anda mengatasi ini?

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$

Baru saja menemukan ini. Saya harus mencatat bahwa saya tidak tahu apa bukti asli Kilian-Alon itu. Satu-satunya pengetahuan saya tentang buktinya adalah dari komunikasi dengan Noga yang tidak ingat detail dari bukti asli, dan bukti yang ia rekontruksi persis seperti ini. Perhatikan bahwa ini juga dapat digambarkan sebagai reduksi deterministik di bawah beberapa asumsi teoritik bilangan kuat (misalnya, bahwa ada bilangan prima dalam setiap interval bentuk [x, x + polylog (x)]).

Boaz Barak

Saya baru saja berbicara dengan Joe Kilian. Dia mengatakan bahwa bukti bahwa dia dan Alon datang dengan melibatkan pengurangan acak tanpa kesalahan. Sejauh yang dia sadari, reduksi deterministik masih terbuka kecuali jika Anda membuat sejumlah asumsi teoretis, seperti yang telah dikatakan Boaz Barak.

Timothy Chow

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

Kutipan dari makalah Madhu :

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

... jauh melampaui kemampuan teori kompleksitas saya :-)

Marzio De Biasi
sumber

Ini hanyalah rumusan lain bahwa masalah ini adalah NP-complete.

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]\}$

Masalah BUKTI SINGKAT di koran hampir sama dengan masalah penghentian yang dibatasi. Pengurangan dari masalah BUKTI SINGKAT kemungkinan besar akan berantakan seperti bukti khas dari NP-kelengkapan SAT, dan oleh karena itu tidak mungkin bahwa bukti NP-kelengkapan dari faktor ini menemukan masalah oleh Kilian membangun pengurangan dari PROOFS PENDEK masalah langsung.

Tsuyoshi Ito

Ini adalah ide pengurangan deterministik informal yang efisien (dan mungkin tidak lengkap):

$\{\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
sumber