Apakah ada bukti bahwa penambahan lebih cepat daripada multiplikasi?

21

Batas atas terbaik yang diketahui pada kompleksitas waktu penggandaan adalah terikat Martin Fürer , yang lebih dari kompleksitas penambahan waktu linear. Apakah kita memiliki bukti bahwa penambahan pada dasarnya lebih mudah daripada perkalian?nlog⁡n2O(log∗⁡n)

cc.complexity-theory time-complexity Hooman
sumber
Mengoreksi batas waktu.
Jeffε
1
lihat juga masalah besar yang belum terpecahkan dalam TCS
vzn
1
itu akan tergantung pada bagaimana Anda mewakili nomor Anda; jika Anda berurusan dengan log penggandaan angka lebih cepat dari penambahan itu (karena membutuhkan pow dan log)
ratchet freak

Jawaban:

30

Tidak.

Tidak ada batas bawah tanpa syarat yang lebih baik daripada trivial saat ini dikenal untuk multiplikasi bilangan bulat. Ada beberapa batas bawah bersyarat sekalipun. Untuk lebih lanjut tentang ini, Anda dapat melihat makalah Faster Integer Multiplication karya Martin Fürer .Ω(n)

Sunting komentar Andrej berikut: Penambahan dapat dilakukan dalam waktu . Sebagai perbandingan, batas atas yang paling dikenal untuk perkalian adalah (kurang-lebih)HAI(n)HAI(nlog⁡n)

Bruno
sumber
Tampaknya bagi saya bahwa makalah ini tidak membuktikan bahwa penambahan lebih cepat daripada perkalian. Haruskah saya berasumsi bahwa belum ada bukti untuk itu?
Hooman
8
Apa yang dikatakan Bruno adalah ini: jelas kita dapat melakukan penambahan dalam waktu linier, dan kita tidak dapat melakukannya lebih cepat daripada dalam waktu linear (karena Anda harus melihat inputnya). Oleh karena itu, menunjukkan bahwa penambahan lebih sulit daripada perkalian adalah hal yang sama dengan menunjukkan bahwa perkalian tidak dapat dilakukan dalam waktu linier. Tetapi tidak ada bukti seperti itu.
Andrej Bauer
2
@ andrej maksudmu "menunjukkan multiplikasi lebih sulit daripada penambahan" kan? poster itu mencampuradukkannya dengan versi pertanyaan sebelumnya. juga berdalih, tidak ada bukti seperti itu diketahui . ini juga tampaknya seperti kandidat yang baik untuk aliran matematika, "masalah terbuka paling 'jelas' dalam teori kompleksitas"
vzn
@vzn itu jawaban yang bagus untuk pertanyaan MO itu, IMO.
Sasho Nikolov
@ SashoNikolov Saya tidak yakin - Saya tidak tahu apakah multiplikasi berada di O (n) akan sangat mengejutkan. Tentu saja kejutan, tetapi AFAIK tidak ada alasan yang baik kecuali dengan analogi dengan masalah seperti penyortiran, transformasi Fourier, dll. Untuk percaya bahwa masalah penggandaan 'alami' O (n ^ 2) tidak dapat disederhanakan sampai ke waktu linier .
Steven Stadnicki