Untuk masalah dalam P apakah lebih mudah untuk memverifikasi hasil daripada menemukannya?

Untuk (versi pencarian) dari masalah NP- lengkap, verifikasi suatu solusi jelas lebih mudah daripada menemukannya, karena verifikasi dapat dilakukan dalam waktu polinomial, sementara menemukan saksi membutuhkan waktu (mungkin) eksponensial.

Dalam P , bagaimanapun, solusinya juga dapat ditemukan dalam waktu polinomial, sehingga tidak tampak jelas kapan verifikasi lebih cepat daripada menemukan solusi. Bahkan, masalah yang berbeda tampaknya berperilaku berbeda dari sudut pandang ini. Beberapa contoh:

1. 3SUM: diberi nomor input , temukan 3 di antaranya yang menjumlahkan ke 0. Sejauh yang saya tahu, algoritma tercepat yang diketahui berjalan dalam waktu , dan urutan ini diperkirakan optimal. Di sisi lain, verifikasi suatu solusi jauh lebih cepat, karena yang perlu kita lakukan hanyalah memeriksa apakah 3 angka yang ditemukan itu berjumlah 0.O ( n 2 - o ( 1 )$n$$O(n^{2-o(1)})$

2. All-Pairs Shortest Paths: diberi grafik dengan bobot tepi, hitung matriks jarak jalur terpendeknya. Setelah matriks seperti itu diberikan, dapatkah ia diperiksa lebih cepat bahwa itu memang matriks jarak yang benar, daripada kembali menghitungnya? Dugaan saya adalah bahwa jawabannya mungkin ya, tetapi jelas kurang jelas daripada untuk 3SUM.

3. Pemrograman Linier. Jika solusi optimal yang diklaim diberikan, memeriksanya lebih mudah daripada menghitung ulangnya, ketika informasi tambahan juga diberikan (solusi ganda optimal). Di sisi lain, jika hanya solusi primal yang tersedia, tidak jelas apakah seseorang dapat memeriksanya lebih cepat, daripada benar-benar menyelesaikan LP.

Pertanyaan: apa yang diketahui tentang subjek ini? Yaitu, kapan lebih mudah memverifikasi suatu solusi untuk suatu masalah di P , daripada menemukan solusinya?

diketahui bahwa diberikan grafik G dan T pohon, dapat diverifikasi dalam waktu linier bahwa T adalah pohon rentang minimum G. Tapi kami belum memiliki algoritma waktu linear deterministik untuk menghitung MST. Tentu saja celahnya kecil (1 vs ), tetapi masih ada :))$\alpha(n)$

Makalah ini menunjukkan bahwa ada verifikasi algoritma untuk kedua YES dan NO kasus selama 3 masalah, termasuk aliran Max, 3SUM, dan APSP, yang lebih cepat oleh faktor polinomial dari batas-batas yang dikenal untuk menghitung solusi itu sendiri.

Ada kelas masalah, yaitu orang-orang yang meningkatkan waktu berjalan adalah SETH-keras, yang waktu berjalan untuk memverifikasi contoh NO tidak mungkin secara signifikan lebih cepat daripada waktu untuk menghitung solusi, jika tidak dugaan dari makalah ini disebut Nondeterministic Hipotesis Waktu Eksponensial yang kuat akan gagal.

Untuk beberapa masalah sepertinya tidak ada perbedaan. Secara khusus, Vassilevska Williams & Williams menunjukkan:

• untuk perkalian matriks Boolean, menghitung produk matriks dan memverifikasi produk matriks yang setara dengan subkubis, yang berarti bahwa mereka berdua memiliki algoritma waktu subkubik atau keduanya tidak.

• Hal yang sama berlaku untuk perhitungan dan verifikasi produk matriks atas setiap "struktur diperpanjang (min, +)" (lihat kertas untuk definisi, tetapi ini mencakup banyak masalah alam).

(Sekarang, tentu saja, ada kemungkinan bahwa semua masalah ini memiliki algoritma subkubis, dan kemudian mungkin ada perbedaan polinom antara komputasi dan verifikasi, tetapi untuk masalah ini tidak mungkin ada perbedaan kubik. Dan tampaknya masuk akal bagi saya bahwa dalam Bahkan mereka semua pada dasarnya membutuhkan waktu kubik.)

• Memutuskan apakah ada nilai dalam array membutuhkan waktu (atau jika array diurutkan).Ω ( log n $\Omega(n)$$\Omega(\log n)$

  Memverifikasi bahwa array berisi nilai yang diberikan pada posisi yang diberikan dimungkinkan dalam waktu .$O(1)$

• Penyortiran (dalam model perbandingan) membutuhkan waktu , tetapi memverifikasi bahwa array atau daftar diurutkan dimungkinkan dalam waktu .O ( n $\Omega(n \log n)$$O(n)$

Saya pikir banyak contoh berasal dari masalah NP-lengkap yang jatuh P ketika kita memperbaiki satu atau lebih parameter .

Misalnya, memeriksa apakah grafik berisi klik ukuran adalah NP-lengkap jika adalah bagian dari input, polinomial-waktu dipecahkan jika diperbaiki.k $k$$k$$k$

Untuk setiap tetap , verifikasi membutuhkan waktu linier, tetapi kecuali , kompleksitas masalah pencarian (polinomial) tergantung pada ( .P = N P k Ω ( n k ) $k$$P=NP$$k$$\Omega(n^k) )$

Contoh lain: menemukan jalur Hamiltonian panjang , mewarnai pada grafik treewidth yang dibatasi, ...$k$

Memutuskan keutamaan: varian AKS yang paling dikenal tampaknya menentukan keutamaan dalam waktu , sedangkan sertifikat Pratt klasik tentang keutamaan menyiratkan keutamaan dapat diputuskan dalam waktu nondeterministik . ˜ O (n3$\tilde{O}(n^6)$$\tilde{O}(n^3)$

Sebuah makalah oleh Abboud et al. baru-baru ini diterima di SODA 2016 menunjukkan bahwa isomorfisma subtree tidak dapat diselesaikan dalam waktu kecuali hipotesis waktu eksponensial yang kuat salah. Tentu saja, kita dapat memverifikasi isomorfisme dalam waktu linier.$O(n^{2-\epsilon})$

Dengan kata lain, SETH memberi kita masalah alami dalam dengan kesenjangan antara menemukan dan memverifikasi. Ω ( n 1 - ϵ$\sf{P}$$\Omega(n^{1-\epsilon})$

Secara khusus, algoritma dikenal untuk pohon berakar, derajat konstan (di mana hasil batas bawah Abboud et al. Masih berlaku). Jadi di bawah SETH, gap find-verifikasi yang hampir linier pada dasarnya ketat untuk masalah ini.$O(n^2/\log n)$