Karakterisasi masalah yang ada algoritma waktu sublinear

Saya bertanya-tanya apakah masalah yang waktu sublinear (dalam ukuran input) algoritma yang ada dapat dicirikan memiliki sifat-sifat tertentu. Ini termasuk waktu sublinear (mis. Pengujian properti, gagasan alternatif perkiraan untuk masalah keputusan), ruang sublinear (mis. Algoritma sketsa / streaming di mana mesin Turing memiliki pita baca-saja, ruang kerja sublinear, dan keluaran hanya-tulis tape) dan pengukuran sublinear (mis pemulihan jarang / penginderaan tekan). Secara khusus, saya tertarik dengan karakterisasi semacam itu untuk kerangka kerja pengujian algoritma properti dan dalam model klasik algoritma acak dan aproksimasi.

Misalnya, masalah yang ada solusi pemrograman dinamis menunjukkan substruktur optimal dan subproblem tumpang tindih; mereka yang memiliki solusi serakah menunjukkan substruktur optimal dan struktur matroid. Dan seterusnya. Referensi apa pun yang berhubungan dengan topik ini dipersilahkan.

Dengan pengecualian beberapa masalah yang mengakui algoritma sub-linear deterministik, hampir semua algoritma sublinear yang saya lihat adalah acak. Apakah ada kelas kompleksitas spesifik yang terkait dengan masalah yang menerima algoritma waktu sublinear? Jika ya, apakah kelas ini termasuk dalam BPP atau PCP?

cc.complexity-theory ds.algorithms complexity-classes approximation-algorithms Massimo Cafaro
sumber

waktu sub-linear dalam model mana?

Kaveh

algoritma pengujian properti berada dalam kerangka umum apa yang Anda inginkan, tetapi poin Kaveh harus dijawab terlebih dahulu.

Suresh Venkat

Saya telah mengedit pertanyaan saya dengan menambahkan informasi yang diminta.

Massimo Cafaro

Transformasi Fourier vektor dapat dihitung dalam waktu sublinear ketika (hampir)

-sparse dalam domain frekuensi. Jadi properti di sini jarang. Lihat misalnya "Algoritma Sederhana dan Praktis untuk Transformasi Sparse Fourier" oleh Haitham Hassanieh, Piotr Indyk, Dina Katabi, dan Harga Eric nms.lcs.mit.edu/~dina/pub/soda12.pdf dan referensi di dalamnya.

k

$k$

Dimitris

Jawaban:

Untuk tugas konstan pengujian properti grafik, karakterisasi yang menarik diketahui. Sebuah properti grafik adalah fungsi dari semua grafik untuk , dan properti grafik adalah diuji jika ada algoritma acak sehingga untuk semua dan semua grafik : $\{0,1\}$ $P$ $A$ $\varepsilon > 0$ $G$

hanya membacatepi dari untuk beberapa fungsi $A(G)$ $g(\varepsilon)$ $G$ $g$
Jika maka output `` ya '' dengan probabilitas tinggi (katakanlah, setidaknya ) $P(G)=1$ $A(G)$ $2/3$
Jika setidaknya tepi harus ditambahkan atau dihapus untuk mendapatkan sehingga (yaitu, adalah jauh dari properti ) maka menghasilkan `` tidak '' dengan probabilitas setidaknya $\varepsilon n^2$ $G$ $G'$ $P(G')=1$ $G$ $\varepsilon$ $A(G)$ $2/3$

Artinya, dapat membedakan antara grafik yang memiliki dan grafik yang memiliki mengedit jarak tinggi dari grafik memiliki . Alon, Fischer, Newman, dan Shapira membuktikan bahwa properti dapat diuji dengan cara ini jika dan hanya jika properti dapat "direduksi" menjadi properti untuk memeriksa apakah grafik memiliki partisi regular (dalam arti Szemeredi) . Ini menunjukkan bahwa pengujian keteraturan "lengkap" untuk pengujian, dalam beberapa hal. (Ada juga versi kesalahan satu sisi pengujian, lihat referensi.) $A$ $P$ $P$ $P$ $\varepsilon$

Ryan Williams
sumber

Di bidang ruang sublinear , tidak ada kelas masalah eksplisit yang menerima solusi ruang sublinear, tetapi ada kelas besar masalah (estimasi momen frekuensi, pengurangan dimensi dll) di mana keberadaan "sketsa" kecil dapat ditunjukkan dan ini mengarah ke algoritma yang efisien.

Tetapi dalam ruang ini juga, algoritme semuanya acak, dan ada batas bawah deterministik yang kuat sebagian besar didasarkan pada kompleksitas komunikasi.

Suresh Venkat
sumber