Program rentang, ukuran saksi, dan kompleksitas sertifikat

Program rentang adalah cara linier-aljabar menentukan fungsi boolean yang diperkenalkan di sini . Baru-baru ini, model ini digunakan untuk menunjukkan bahwa metode musuh negatif memberikan karakterisasi yang ketat (setidaknya hingga ) dari kompleksitas kueri. $\log n/ \log \log n$

Ukuran kompleksitas yang menghubungkan program rentang ke kompleksitas permintaan kuantum adalah ukuran saksi. Ukuran ini tampaknya agak mirip dengan kompleksitas sertifikat. Adakah hubungan yang diketahui antara kedua tindakan? Bagaimana dengan ukuran (jumlah vektor input) untuk rentang program dan ukuran lain seperti kompleksitas kueri deterministik dan acak? Apa algoritma klasik paling terkenal untuk mengevaluasi program rentang?

EDIT (setelah jawaban oleh Martin Schwarz):

Yang menarik adalah koneksi konseptual yang langsung melalui program rentang sebagai lawan melalui korespondensi antara ukuran saksi dan kompleksitas kueri kuantum. Adakah hasil klasik yang memberikan intuisi tentang rentang program / ukuran saksi dan bagaimana kaitannya dengan kompleksitas kueri deterministik dan acak?

cc.complexity-theory reference-request quantum-computing query-complexity Artem Kaznatcheev
sumber

Jawaban:

Ukuran saksi minimum untuk semua saksi program rentang untuk fungsi yang diberikan sama dengan batas musuh yang digeneralisasi, seperti yang ditunjukkan misalnya dalam Teorema 1.7 di sini . Selanjutnya,~~digeneralisasi~~batas musuh hanyalah relaksasi semi-pasti kompleksitas sertifikat, lihat misalnya slide 40 dalam tutorial Reichardt . Hubungan dengan kompleksitas permintaan deterministik dan acak juga dibahas dalam slide tutorial ini.

Martin Schwarz
sumber

f

$f$

C (f) = 3

$C(f) = 3$

A D V^{\pm} (f) = 2 + 3 \sqrt{5} / 5 > 3

$ADV^{\pm}(f) = 2 + 3\sqrt{5}/5 > 3$

Baiklah saya setuju. Jadi argumen relaksasi tampaknya benar-benar hanya berlaku untuk langkah dari C (f) ke ADV (f). Bagaimanapun, saya pikir slide 40 yang saya maksud di atas dengan baik merangkum langkah-langkah generalisasi yang diambil dari C (f) melalui relaksasi ke ADV (f) dan kemudian melalui generalisasi lain ke ADV ± (f), yang merupakan hubungan antara C (f) ) dan ADV ± (f) yang Anda tanyakan.

Martin Schwarz

Terima kasih atas jawabannya. Koneksi semacam ini berjalan langsung melalui kompleksitas kueri dan berhubungan dengan pertanyaan sebelumnya , tapi saya rasa saya mencoba mencari koneksi langsung lebih banyak melalui program span. Secara khusus saya mencoba untuk mendapatkan lebih banyak wawasan tentang program rentang sendiri tanpa menggunakan pengetahuan saya tentang kompleksitas kueri kuantum. Saya akan mengedit pertanyaan saya untuk membuatnya lebih jelas dan melihat apakah itu menghasilkan wawasan lebih lanjut ke dalam program span.

Artem Kaznatcheev