kompleksitas pembagi umum terbesar (gcd)

33

Pertimbangkan masalah penghitungan berikut (atau masalah keputusan terkait): Diberi dua bilangan bulat positif yang dikodekan dalam biner, hitung pembagi bersama terbesarnya (gcd). Apa kelas kompleksitas terkecil dari masalah ini? Bisakah Anda memberikan referensi?

Dalam pertanyaan ini saya terutama tidak tertarik pada batas asimptotik pada waktu berjalan, tetapi lebih pada kelas kompleksitas. Apakah masalah pada AC? Bisakah dibuktikan tidak berbohong pada AC0? Apa kelas kompleksitas lain di dalam P yang relevan di sini?

cc.complexity-theory reference-request complexity-classes nt.number-theory Felix Breuer
sumber
3
@ Jo: Penafsiran saya adalah bahwa penanya tertarik pada apakah bahasa {(x, y, i) | bit ke-i dari gcd (x, y) adalah 1} ada di NC, AC0, dll., tetapi klarifikasi oleh penanya akan berguna.
Tsuyoshi Ito
1
Ya, ungkapan Tsuyoshi tentang masalah keputusan adalah apa yang ada dalam pikiran saya - maaf untuk ambiguitas. Namun, tolong jangan fokus pada kelas kompleksitas yang saya sarankan, karena saya tidak tahu kelas kompleksitas mana yang relevan di sini. Saya ingin tahu tentang kelas kompleksitas nontrivial yang merupakan subset dari P (atau FP, resp.) Yang berisi gcd.
Felix Breuer
1
Saya ingin tahu tentang kasus bilangan bulat gaussian. Pencarian google cepat menunjukkan cara untuk mengadaptasi algoritma euclidean normal, tetapi tidak ada yang membahas hubungan antara bilangan asli dan bilangan bulat gaussian. Apakah ada algoritma gcd di atas bilangan asli memberi kita algoritma di atas bilangan gaussian dengan kompleksitas yang sama? (Saya tidak punya aplikasi, ini rasa ingin tahu yang murni.) Juga, apakah ada algoritma acak yang efisien untuk menghitung GCD dengan waktu berjalan yang lebih rendah?
Ross Snider
1
Lihat juga cstheory.stackexchange.com/questions/2708/…
Zsbán Ambrus
1
Tautan yang diperbaiki : mathoverflow.net/questions/44684/… . Terima kasih atas peringatannya, Kaveh.
Zsbán Ambrus

Jawaban:

44

Ini adalah pertanyaan terbuka utama dalam teori kompleksitas: tidak diketahui apakah GCD dapat dihitung dalam NC, dan tidak diketahui apakah komputasi GCD adalah P-complete. Algoritma paralel terbaik memang memiliki waktu berjalan paralel sub-linear, salah satunya disebabkan oleh Sorenson:

J. Sorenson. Dua algoritma GCD cepat . Jurnal Algoritma, 1994.

Jika saya tidak salah, bahkan tidak diketahui jika seseorang dapat memutuskan apakah dua bilangan bulat relatif prima di NC.

John Watrous
sumber
Terima kasih, itu yang ingin saya ketahui! Namun, jika seseorang mengetahui subset nontrivial P lainnya yang diketahui mengandung gcd, beri tahu saya.
Felix Breuer
15
Pengujian jika dua bilangan bulat relatif prima juga terbuka menurut referensi ini: Batas untuk komputasi paralel , halaman 231, masalah B.5.7.
Robin Kothari
4
Referensi yang sangat baru adalah: Sorenson, Jonathan P. "Algoritma GCD paralel waktu sublinear acak untuk EREW PRAM." Pemrosesan Informasi Letters 110, no. 5 (Februari 2010): 198-201. linkinghub.elsevier.com/retrieve/pii/S0020019009003640 .
Felix Breuer
3

Makalah ini , yang diterbitkan pada 2007, mengatakan bahwa integer GCD ada di NC.

Sunting: Pernyataan itu mungkin salah. Periksa komentarnya.

Apoorv Gupta
sumber
4
Makalah ini tidak pernah diterbitkan , hanya diposting di situs web penulis. Selain itu, penulis sendiri tampaknya tidak percaya makalah 2007-nya benar, karena ia mencantumkan masalah sebagai terbuka di makalah-makalahnya nanti ( cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci09.pdf ).
Emil Jeřábek mendukung Monica
Tidak tahu itu. Terima kasih telah menunjukkannya.
Apoorv Gupta
1
Saya tidak berpikir jawaban semacam ini harus diturunkan.
Alessandro Cosentino