Apa hubungan antara hipotesis-hipotesis dalam Fine-Grained Complexity Theory?

Teori kompleksitas, melalui konsep-konsep seperti NP-kelengkapan, membedakan antara masalah komputasi yang memiliki solusi yang relatif efisien dan yang tidak bisa dipecahkan. Kompleksitas "berbutir halus" bertujuan untuk menyaring perbedaan kualitatif ini menjadi panduan kuantitatif tentang waktu yang dibutuhkan untuk menyelesaikan masalah. Rincian lebih lanjut dapat ditemukan di sini: http://simons.berkeley.edu/programs/complexity2015

Berikut ini beberapa hipotesis penting:

ETH: - membutuhkan waktu untuk beberapa .S A T 2 δ n δ > $3$$SAT$$2^{\delta n}$$\delta > 0$

SETH: untuk setiap , ada sedemikian sehingga - pada variabel, klausa tidak dapat diselesaikan dalam .k k S A T n m 2 ( 1 - ε ) n p o l y $\varepsilon > 0$$k$$k$$SAT$$n$$m$$2^{(1-\varepsilon)n}~poly~m$

Diketahui bahwa SETH lebih kuat dari ETH dan mereka berdua lebih kuat dari , dan keduanya lebih kuat dari .F T P ≠ W [ 1 $P \neq NP$$FTP\neq W[1]$

Empat dugaan penting lainnya:

1. 3SUM dugaan: 3SUM pada bilangan bulat di membutuhkan waktu{ - n 3 , … , n 3 } n 2 - o ( 1 $n$$\{-n^3,…,n^3\}$$n^{2-o(1)}$

2. Dugaan OV: Vektor ortogonal pada vektor membutuhkan waktu .n 2 - o ( 1 $n$$n^{2-o(1)}$

3. Dugaan APSP: Semua Pasang Jalur Terpendek pada node dan bobot bit membutuhkan waktu .O ( log n ) n 3 - o ( 1 $n$$O(\log n)$$n^{3-o(1)}$

4. Konjektur BMM: Algoritma "kombinatorial" apa pun untuk perkalian matriks Boolean memerlukan waktu .$n^{3-o(1)}$

Diketahui bahwa SETH mengimplikasikan dugaan OV (Ryan Willams, 2004). Selain bukti Ryan bahwa SETH dugaan OV, tidak ada pengurangan lain terkait dugaan tersebut.$\implies$

Pertanyaan saya: Apakah Anda tahu hipotesis atau dugaan terkait lainnya di bidang ini? Apa hubungan di antara mereka?

Pengakuan: hasil yang terdaftar berasal dari slide Virginia Vassilevska Williams, dia juga memberi saya sebagian jawaban untuk pertanyaan ini.

Tautan ke slide: http://theory.stanford.edu/~virgi/overview.pdf

Ini adalah makalah baru - baru ini memperkenalkan Nondeterministic Strong Exponential Time Hypothesis (NSETH), yang merupakan perpanjangan dari SETH.

NSETH: Untuk setiap , ada k sehingga k -DNF-TAUT tidak dapat diselesaikan dalam waktu nondeterministik 2 ( 1 - ϵ ) n .$\epsilon >0$$k$$k$$2^{(1-\epsilon)n}$

NSETH menyiratkan SETH. Jika NSETH benar, maka beberapa masalah tidak memiliki batas SETH lebih rendah (karena mereka memiliki algoritma nondeterministic lebih cepat daripada algoritma deterministik).

Makalah ini juga memperkenalkan Non-seragam Nondeterministic Strong Exponential Time Hypothesis (NUNSETH), sebuah hipotesis yang lebih kuat dari NSETH dan SETH.

NUNSETH: Untuk setiap , ada k sedemikian sehingga k -DNF-TAUT tidak dapat dikenali oleh keluarga rangkaian nondeterministik ukuran 2 ( 1 - ϵ ) n .$\epsilon >0$$k$$k$$2^{(1-\epsilon)n}$

Dugaan menarik lainnya adalah kekerasan -Clique untuk fixed k (lihat di sini ).$k$$k$

Ini bukan jenis hubungan yang Anda cari, tetapi ada makalah FOCS menarik yang menunjukkan bahwa masalah alami yang disebut "Matching Segitiga" sulit di bawah salah satu dugaan SETH, 3SUM, atau APSP (lihat di sini ). Saat ini tidak diketahui apakah salah satu dari ketiga dugaan ini menyiratkan satu sama lain dengan cara yang menarik - ini adalah salah satu pertanyaan terbuka utama dari Fine-Grained Complexity.

$O(n^{2-\epsilon})$

• Edit Jarak Tidak Dapat Dihitung dalam Waktu Sangat Subquadratic (kecuali SETH salah) / Backurs, Indyk

• Peta Baru Melacak Batas Komputasi / Pavlus, majalah Quanta

• Selama 40 tahun, para ilmuwan komputer mencari solusi yang tidak ada / Boston Globe

• Bukti membingungkan / blog RJLipton

$O(n^{2-\epsilon})$

• Memutuskan kekosongan persimpangan bahasa reguler dalam waktu subquadratic / cstheory SE

$k$$n^{o(k)}$$NL \subsetneq P$

• Hasil Kekerasan untuk Persimpangan Non-Kekosongan / Wehar

sepanjang garis ini juga perlu disebutkan ada hubungan signifikan yang diketahui antara konstruksi DFA dan perhitungan jarak Levenshtein misalnya dalam makalah ini

• Koreksi string cepat dengan Levenshtein automata / Shulz, Mihov