Apakah menulis angka sebagai dua kotak dan menulis faktor-faktor angka sama sulitnya?

Membiarkan $L_1$ dan $L_2$ menjadi yang berikut:

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

Klaim $L_1 \leq_P L_2$

Bukti Sketsa

Jika saya ingin tahu apakah $r\in L_1$ .

Jumlah solusi integer untuk $x^2+y^2=r$ diberikan oleh

$g(r)=\sum_{d|r}{\chi{(d)}}$ dimana $\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 }$

Kemudian $L_1=\{r: g(r)\neq 0\}$ . Maka yang harus dijawab adalah " $r\in L_1$ ? "Apakah paling sulit untuk menjawab sebagai" apa pembagi $r$ ? "

$\square$

Yang ingin saya ketahui adalah apakah ini benar sebaliknya. Apakah benar kalau saya punya mesin yang bisa memberi tahu saya dalam waktu yang konstan apakah $r\in L_1$ bisakah saya membuat mesin yang bisa menjawab "adalah $(M,N)\in L_2$ ? "dalam waktu polinomial?

Motivasi

Pertanyaan ini keluar dari diskusi tentang pertanyaan ini .

Maaf saya benar-benar hanya anggota math.se yang tersesat dan berjalan ke cs.se. Beri tahu saya jika pertanyaan saya jelas dan memenuhi standar situs ini. Saya senang melakukan koreksi.

complexity-theory time-complexity np decision-problem Tukang batu
sumber

Apakah saya menggunakan

\leq_{P}

$\leq_P$ benar?

Mason

Pengurangan Anda

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

$L_1\le_p L_2$ benar, tetapi kesimpulan Anda itu

L_{1}

$L_1$ "sekeras"

L_{2}

$L_2$ salah. Anda hanya menunjukkan itu

L_{1}

$L_1$ adalah paling sekeras

L_{2}

$L_2$ . Secara khusus, Anda benar-benar menunjukkan itu

L_{1}

$L_1$ paling keras seperti kasus yang sangat terbatas

L_{2}

$L_2$ , yang mungkin sangat mudah.

Shaull

Alih-alih "memuaskan lingkaran", istilah yang lebih baik bisa "menjadi jumlah dari dua kotak".

Yuval Filmus

@ Samull, saya mengubah beberapa bahasa untuk mencerminkan komentar Anda.

Mason

Komputasi

\sum_{d ∣ n} d

$\sum_{d\mid n}d$ sebenarnya diketahui sama sulitnya dengan anjak piutang, hingga pengurangan waktu polinomial secara acak. Lihat Bach, Miller, dan Shallit: Jumlah pembagi, angka sempurna, dan anjak piutang .

Emil Jeřábek

Jawaban:

Inilah situasinya sejauh yang saya tahu:

Cara paling efisien untuk menguji keanggotaan di $L_1$ adalah faktor $r$ . Tidak ada algoritma yang lebih efisien yang diketahui.

Namun, tidak ada pengurangan yang jelas untuk dibuktikan $L_2 \le_P L_1$ . Dengan kata lain, jika kita memiliki mesin untuk memutuskan $L_1$ , tidak ada cara mudah untuk menggunakannya untuk memfaktorkan. Jika kita ingin memfaktorkan angka $N$ , kita dapat memeriksa apakah $N \in L_1$ , tetapi ini hanya memberi kami sedikit informasi tentang faktor $N$ . Menguji kelipatan $N$ (yaitu apakah $cN \in L_1$ untuk beberapa integer $c$ ) tidak memberi kami informasi tambahan, seperti mengetahui apakah $N \in L_1$ cukup untuk memprediksi apakah $cN \in L_1$ untuk semua $c>0$ . Menguji nomor lain juga tidak membantu. (Menguji apakah $N' \in L_1$ untuk beberapa nomor lainnya $N'$ sepertinya tidak memberikan informasi yang berguna, jika $\gcd(N,N') =1$ ; dan jika kita memiliki cara untuk menemukan nomor lain sedemikian rupa sehingga , kita sudah tahu bagaimana faktornya, tetapi tentu saja kita tidak tahu bagaimana melakukannya - jadi nomor berapa pun yang kami tahu cara menghasilkan tidak mungkin memberi kami informasi yang berguna tentang faktor-faktor ) Ini bukan bukti; itu hanya intuisi tangan. $N'$ $\gcd(N,N')\ne 1$ $N$

Jadi tampaknya masuk akal bahwa mungkin lebih mudah daripada , dan juga masuk akal bahwa mereka mungkin memiliki kesulitan yang sama. Saya tidak mengetahui adanya hasil lebih lanjut tentang hal ini. $L_1$ $L_2$

DW
sumber