Versi multiplikasi 3-SUM

22

Apa yang diketahui tentang kompleksitas waktu dari masalah berikut, yang kita sebut 3-MUL?

Diberikan himpunan dari bilangan bulat, apakah ada elemen sedemikian sehingga ?Sna,b,cSab=c

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?a,b,cSa+b+c=0a+b=cn

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.SSS={2xxS}2a2b=2ca+b=c

Markus Jalsenius
sumber
Pengurangan Anda menunjukkan bahwa 3-MULT adalah 3-SUM sulit jika angka input dapat dinyatakan menggunakan notasi eksponensial (alias ilmiah).
Warren Schudy
4
Algoritma apa pun untuk 3-SUM yang hanya mengandalkan fakta bahwa penjumlahan adalah grup dapat diterjemahkan ke dalam algoritme untuk 3-MULT, dan sebaliknya. Algoritme apa pun yang memisahkan keduanya perlu melakukan sesuatu yang tidak biasa dengan angka-angkanya.
Warren Schudy
1
untuk menjadi sangat mengerikan, kita mungkin hanya perlu setengah-kelompok.
Suresh Venkat

Jawaban:

11

Pengurangan Anda dari 3 SUM menjadi 3 MUL berfungsi dengan modifikasi standar minor. Misalkan bilangan bulat asli Anda ada di { 1,,M }. Setelah transformasi x2x 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,cSabc<2Mn3qabc2Mn3

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 SP2Mn4O(Mn4logMn)pPpabcaSp3ab=c , Dengan probabilitas tinggi akan benar untukinstance 3 SUMasli. Kami telah mengurangi rentang angka menjadi { 0 , ... , O ( M n 4 log M n ) }.S30,,O(Mn4logMn)

(Ini adalah pengurangan ukuran standar Anda mungkin bisa berbuat lebih baik dengan mempertimbangkan fakta bahwa. selalu perbedaan dari dua kekuatan dari 2 .)abc2

virgi
sumber
1
Tidakkah Anda direduksi menjadi 3MUL mod a prime daripada 3MUL? Mungkin tetapi . a b cab=c(mod()p)abc
Warren Schudy
1
Ya, sebagaimana adanya, ini merupakan pengurangan ke 3MUL mod p. Poin bagus.
virgi
Ini adalah pendekatan yang sangat menarik. Namun, kami terutama tertarik pada pengurangan deterministik dari 3-SUM ke 3-MUL. Apakah mungkin untuk derandomise teknik pengurangan ukuran?
Markus Jalsenius
3

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|xS}M=maxSminS

Warren Schudy
sumber
Ups, derau acak sepertinya tidak cukup untuk memperbaiki kesalahan pembulatan. Namun ide-ide ini tampaknya menjanjikan untuk mengurangi cara lain untuk menunjukkan 3-MULT tidak lebih sulit dari 3-SUM, karena misalnya . (x+1)+y=x+y+1
Warren Schudy
1
Persamaannya tampaknya tidak benar (coba x dan y = 2.1). Bisakah Anda mengklarifikasi apa yang Anda maksud?
Raphael