Bagaimana P =? NP meningkatkan faktorisasi bilangan bulat

14

Jika sebenarnya sama dengan , bagaimana hal ini akan meningkatkan algoritma kami menjadi faktor integer lebih cepat. Dengan kata lain, wawasan seperti apa yang akan diberikan fakta ini dalam memahami faktorisasi bilangan bulat lebih baik?PNP

Mike G
sumber

Jawaban:

9

Jika , dan kami memiliki algoritma yang dapat memecahkan masalah k-SAT dalam waktu polinomial, maka faktorisasi bilangan bulat dapat direduksi menjadi k-SAT dengan menggambarkan faktorisasi sebagai masalah dalam k-SAT.P=NP

Pada dasarnya ini berfungsi sebagai berikut: Anda membuat banyak variabel yang masing-masing mewakili bit , dan , dan . Kemudian Anda merumuskan masalah k-SAT sebagai . Karena diketahui, Anda dapat mengatur nilai-nilai itu. Kemudian tugas yang memuaskan akan menggambarkan dan valid . Untuk menggambarkan perkalian dalam k-SAT, Anda dapat menggunakan salah satu dari algoritma pengali yang diketahui dan menggambarkan rangkaian logisnya di k-SAT. Untuk info lebih lanjut tentang mengurangi anjak piutang menjadi k-SAT, lihat di sini .halqnhalq=nnhalq

Adapun untuk memahami anjak lebih baik, itu mungkin akan membutuhkan lebih banyak penelitian dan menganalisis algoritma ajaib (yang dapat memecahkan masalah NP-lengkap dalam waktu polinomial deterministik), dan mungkin mengkhususkannya untuk perumusan bilangan bulat k-SAT masalah formulasi k-SAT (yang jelas memiliki struktur yang sangat spesifik, tergantung pada algoritma perkalian yang digunakan).

Realz Slaw
sumber
3

Masalah keputusan untuk anjak piutang adalah dan anjak piutang dapat dikurangi menjadi waktu polinomial deterministik.NP

Jika maka masalah apa pun di termasuk anjak akan memiliki algoritma waktu polinomial.P=NPNP

Perhatikan bahwa algoritma deterministik / probabilistik yang paling dikenal untuk anjak pada saat ini membutuhkan waktu eksponensial sehingga algoritma waktu polinomial akan menjadi peningkatan yang hebat. Untuk mendapatkan perasaan itu, pertimbangkan anjak nomor 2000 bit. Yang satu mungkin membutuhkan waktu lebih lama daripada sejak big bang, yang lain mungkin menjawab dalam beberapa milidetik.

Kaveh
sumber
hanya untuk memperjelas OP: versi keputusan umum dari anjak piutang adalah "apakah angka memiliki faktor Y sedemikian sehingga 1 < Y < K ", di mana X dan K adalah input. sertifikat hanyalah angka Y yang memenuhi persyaratan. masalah keputusan dapat digunakan untuk benar-benar faktor dengan melakukan pencarian biner pada K sampai faktor yang tepat tunggal X ditemukan dan kemudian recurse di X / Y . XY1<Y<KXKYKXX/Y
Sasho Nikolov