Apa yang diketahui tentang kompleksitas waktu dari masalah berikut, yang kita sebut 3-MUL?
Diberikan himpunan dari bilangan bulat, apakah ada elemen sedemikian sehingga ?
Masalah ini mirip dengan masalah 3-SUM, yang menanyakan apakah ada tiga elemen sehingga (atau ekuivalen ). 3-SUM diperkirakan membutuhkan waktu kuadratatik dalam . Apakah ada dugaan serupa untuk 3-MUL? Secara khusus apakah 3-MUL dikenal sebagai 3-SUM sulit?
Catatan, kompleksitas waktu harus diterapkan dalam model perhitungan yang "masuk akal". Misalnya, kita dapat mengurangi dari 3-SUM pada himpunan ke 3-MUL pada himpunan , di mana . Maka solusi untuk 3-MUL, , ada jika dan hanya jika . Namun, ledakan angka yang eksponensial ini sangat buruk dengan berbagai model, seperti model RAM misalnya.
sumber
Jawaban:
Pengurangan Anda dari3 SUM menjadi 3 MUL berfungsi dengan modifikasi standar minor. Misalkan bilangan bulat asli Anda ada di { 1,…,M }. Setelah transformasi x→2x bilangan bulat baru berada di { 2,…,2M }. Kami akan mengurangi jangkauan.
Pertimbangkan triple integer pada set S ′ yang baru . Jumlah pembagi utama dari setiap nol a b - c adalah < 2 M . Jumlah tiga kali lipat tersebut adalah n 3 . Oleh karena itu jumlah bilangan prima q yang membagi setidaknya satu dari a b - c bilangan nol paling banyak 2 M n 3 .a,b,c S′ ab−c <2M n3 q ab−c 2Mn3
Biarkan menjadi himpunan 2 M ⋅ n 4 bilangan prima pertama. Ukuran prime terbesar adalah paling banyak O ( M n 4 log M n ) . Memilih seorang perdana acak p ∈ P . Dengan probabilitas tinggi p tidak akan membagi sembarang nol a b - c , sehingga kita dapat mewakili masing - masing a ∈ S ′ dengan residu, mod p , dan jika 3 MUL menemukan beberapa a b = c di SP 2M⋅n4 O(Mn4logMn) p∈P p ab−c a∈S′ p 3 ab=c , Dengan probabilitas tinggi akan benar untukinstance 3 SUMasli. Kami telah mengurangi rentang angka menjadi { 0 , ... , O ( M n 4 log M n ) }.S′ 3 0,…,O(Mn4logMn)
(Ini adalah pengurangan ukuran standar Anda mungkin bisa berbuat lebih baik dengan mempertimbangkan fakta bahwa. selalu perbedaan dari dua kekuatan dari 2 .)ab−c 2
sumber
Sudahkah Anda mencoba reduksi mana ? Hasilnya adalah bilangan real sehingga Anda harus membulatkan ke beberapa angka. Untuk memastikan bahwa angka-angka bertambah dengan benar meskipun ada pembulatan, Anda mungkin perlu menambahkan sedikit noise acak.S′={2x/M|x∈S} M=maxS−minS
sumber