Trade off antara waktu dan kompleksitas permintaan

Bekerja secara langsung dengan kompleksitas waktu atau batas bawah sirkuit menakutkan. Karenanya, kami mengembangkan alat seperti kompleksitas kueri (atau kompleksitas pohon keputusan) untuk menangani batasan yang lebih rendah. Karena setiap kueri mengambil setidaknya satu langkah unit, dan perhitungan antara kueri dihitung sebagai bebas, kompleksitas waktu paling tidak setinggi kompleksitas kueri. Namun, bisakah kita mengatakan sesuatu tentang pemisahan?

Saya ingin tahu tentang karya dalam literatur klasik, atau kuantum, tetapi memberikan contoh dari QC karena saya lebih akrab.

Beberapa algoritma terkenal seperti pencarian Grover dan penemuan periode Shor, kompleksitas waktu berada dalam faktor-faktor poli-logaritmik dari kompleksitas kueri. Untuk yang lain, seperti Masalah Subkelompok Tersembunyi, kami memiliki kompleksitas kueri polinomial , namun algoritma waktu polinomial tidak diketahui.

Karena ada celah yang berpotensi antara kompleksitas waktu dan kueri, tidak jelas bahwa algoritma kompleksitas waktu yang optimal harus memiliki kompleksitas kueri yang sama dengan algoritma kompleksitas kueri yang optimal.

Apakah ada contoh kompromi antara kompleksitas waktu dan kueri?

Apakah ada masalah di mana algoritma kompleksitas waktu yang paling dikenal memiliki kompleksitas kueri yang berbeda dari algoritma kompleksitas kueri yang paling dikenal? Dengan kata lain, dapatkah kita melakukan lebih banyak kueri untuk membuat operasi antar-kueri lebih mudah?

Atau adakah argumen yang menunjukkan bahwa selalu ada versi algoritma permintaan optimal asimptotik yang memiliki implementasi dengan kompleksitas waktu terbaik asimptotik?

Berikut adalah upaya membuat fungsi buatan dengan properti berikut:

• Masalahnya dapat diselesaikan dengan kueri , tetapi membutuhkan waktu exp ( n ) .$O(\log n)$$\exp(n)$
• Masalahnya dapat diselesaikan dengan waktu tetapi itu membutuhkan O ( n ) query$O(n)$$O(n)$

Biarkan ukuran input menjadi . Biarkan log pertama n bit (sebut string ini x) menyandikan input ke masalah lengkap untuk EEXP. N bit berikutnya (sebut saja string ini y) memiliki properti yang semuanya nol jika dan hanya jika x adalah NO instance dari masalah EEXP-complete.$n + \log n$$\log n$$n$

Dengan kata-kata, bit pertama menyandikan masalah yang sulit, dan n bit berikutnya memberi Anda petunjuk tentang solusi masalah. Namun, untuk mencari solusinya dengan melihat string n bit Anda membuat Ω ( n ) query.$\log n$$n$$n$$\Omega(n)$

Jadi masalah ini dapat diselesaikan dengan hanya membaca bit pertama dan menghabiskan exp (n) waktu atau dengan membaca n bit dan hanya menggunakan waktu linear.$\log n$$n$

Fungsi yang sama berlaku untuk kompleksitas kueri kuantum .. masukkan tanda-tanda root kuadrat jika perlu.

Versi yang lebih ekstrim dari contoh Robin:

Biarkan ukuran input menjadi , dengan n - 1 bit pertama (sebut string ini x ) mengkode mesin Turing T x . Perbaiki beberapa fungsi f ( n ) . Biarkan bit terakhir dari string menjadi 1 jika mesin Turing T x berhenti dalam kurang dari langkah f ( n ) . Masalahnya kemudian untuk menentukan apakah T x berhenti dalam kurang dari f ( n ) langkah dan paritas x adalah genap.$n$$n-1$$x$$T_x$$f(n)$$1$$T_x$$f(n)$$T_x$$f(n)$$x$

Dengan demikian, dengan membuat query masalah dapat diselesaikan dalam waktu O ( f ( n ) ) , sementara dengan membuat n query, masalah dapat diselesaikan dalam waktu O ( n ) .$n-1$$O(f(n))$$n$$O(n)$

Saya suka jawaban Robin Kothari dan modifikasi Joe Fitzsimons. Dalam ekstensi jawaban mereka yang jelas mereka dapat mencapai rasio pemisahan apa pun (kecuali konstan-vs-tidak-konstan) antara kompleksitas kueri yang lebih kecil dan lebih besar dan kompleksitas waktu yang lebih besar dan lebih kecil. Namun, tidak ada cara yang jelas untuk membuat fungsinya non-parsial. Saya ingin menunjukkan masalah alami di mana kami memiliki pemisahan dan menunjukkan bahwa pemisahan besar lebih sulit untuk fungsi total.

Masalah alami

Ben Reichardt menunjukkan melalui email masalah evaluasi formula. Kompleksitas kueri kuantum untuk mengevaluasi rumus AND-OR baca-sekali umum pada variabel adalah Θ ( $n$. Namun,O($\Theta(\sqrt{n})$Algoritma query tidak efisien waktu. Di sini, algoritma yang paling cepat diketahui ditunjukkan untuk menghasilkanO($O(\sqrt{n})$kueri dan jalankan dalam waktu secara polilogaritma lebih buruk. Jadi kita memiliki masalah total alami di mana ada pemisahan yang diketahui. Meskipun tidak ada bukti bahwa pemisahan ini harus ada.$O(\sqrt{n}\log{n})$

Fungsi total lebih sulit dipisahkan?

Bagi saya, sepertinya lebih sulit untuk menemukan fungsi total dengan pemisahan yang dapat dibuktikan. Untuk menunjukkan bahwa kasus fungsi total dan parsial berbeda, saya akan memberikan argumen tentang pemisahan terbesar antara kerumitan kueri dari algoritma kueri-optimal dan waktu-optimal untuk fungsi total.

$m$$\Omega{(\log m)}$$m$$n$$n - m$$m$$0$

, kemudian untuk fungsi total, diberikan algoritma query-optimal dengan kompleksitas ( q 1 ( n ) , t 1 ( n ) ) , ada algoritma optimal-waktu dengan kompleksitas ( q $(\text{query complexity}\; , \; \text{time complexity})$$(q_1(n),t_1(n))$$(q_2(n),t_2(n))$$q_2(n) \leq f(q_1(n))$$f(n) = O(2^n)$

[1] HU Simon, "A Z ketat (loglogn) - terikat pada waktu untuk paralel RAM untuk menghitung fungsi Boolean non-merosot", di: Symp. tentang Yayasan Teori Komputasi, Catatan Kuliah di Ilmu Komputer, Vol. 158, Springer, Berlin, 1983, hlm. 439-444.