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

52

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 ) )nO(n2o(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?

Andras Farago
sumber
7
Saya pikir banyak contoh berasal dari masalah NP-lengkap yang jatuh P ketika kita memperbaiki beberapa parameter. Misalnya, memeriksa apakah grafik berisi klik ukuran untuk tetap . Verifikasi membutuhkan waktu linier, tetapi kecuali P = NP, kompleksitas masalah pencarian (polinomial) tergantung padak kkkk
Marzio De Biasi
16
Kami dapat memverifikasi bahwa daftar bilangan bulat diurutkan dengan perbandingan , tetapi diperlukan perbandingan untuk mengurutkan daftar yang tidak disortir. n - 1 Θ ( n log n )nn1Θ(nlogn)
Thomas
7
Apakah Anda ingin mudah memverifikasi ya dan tidak ada contoh untuk masalah keputusan? Untuk 3SUM, sementara itu mudah untuk memverifikasi contoh ya dalam waktu yang konstan, saya tidak tahu apakah itu mudah untuk memverifikasi contoh tidak. Atau apakah Anda lebih memikirkan masalah di mana ada keluaran non-Boolean, seperti perkalian matriks? (Perkalian matriks adalah contoh dari apa yang Anda inginkan jika Anda mengizinkan algoritma acak.)
Robin Kothari
3
"Di sisi lain, verifikasi suatu solusi jauh lebih cepat, karena yang perlu kita lakukan hanyalah memeriksa apakah 3 angka yang ditemukan itu benar-benar berjumlah 0." - Kita juga perlu memeriksa bahwa 3 angka yang ditemukan sebenarnya adalah bagian dari input.
hvd
3
Adakah masalah yang kami tahu bahwa verifikasi tidak mudah?
Raphael

Jawaban:

24

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 :))α(n)

Suresh Venkat
sumber
4
Mungkin adil untuk menambahkan bahwa ada algoritma acak yang berjalan dalam waktu linier yang diharapkan (algoritma Karger-Klein-Tarjan).
Sasho Nikolov
2
Juga, kalau-kalau ada yang menginginkan tautan, ini adalah algoritma verifikasi MST linear-time paling sederhana yang saya ketahui: webhome.cs.uvic.ca/~val/Publications/Algorithmica-MSTverif.ps .
Sasho Nikolov
20

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.

Thatchaphol
sumber
18

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.)

Joshua Grochow
sumber
2
Di sisi lain, untuk perkalian matriks dalam bidang yang cukup besar, ada algoritma waktu kuadratik acak untuk verifikasi, sedangkan waktu tercepat untuk menghitung produk adalah n ^ omega.
Thatchaphol
2
@Thatchaphol: Ya, meskipun banyak orang percaya omega = 2 ... Juga, secara luas diakui bahwa perkalian matriks Boolean (yaitu menghitung matriks mult di atas Boolean dan-atau semi-ring) memiliki sifat yang agak berbeda daripada perkalian matriks atas suatu bidang.
Joshua Grochow
16
  • Memutuskan apakah ada nilai dalam array membutuhkan waktu (atau jika array diurutkan).Ω ( log n )Ω(n)Ω(logn)

    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 )Ω(nlogn)O(n)

Raphael
sumber
2
Serupa: menentukan apakah ada elemen duplikat adalah dalam model perbandingan, tetapi tentu saja dapat diverifikasi dalam . O ( 1 )Ω(nlogn)O(1)
SamM
@ Sam: Maksud Anda diverifikasi di ? Apa yang Anda berikan sebenarnya? Saya merasa seperti Anda membuat perbandingan yang tidak adil. O(n)
Mehrdad
@Mehrdad poin bagus; jika Anda diberi nilai (bukan indeks), harus memverifikasi. Saya dapat melihat argumen yang bagus bahwa ini adalah cara yang lebih baik untuk melihatnya. Θ(n)
SamM
10

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 kkkk

Untuk setiap tetap , verifikasi membutuhkan waktu linier, tetapi kecuali , kompleksitas masalah pencarian (polinomial) tergantung pada ( .P = N P k Ω ( n k ) )kP=NPkΩ(nk))

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

Marzio De Biasi
sumber
9

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)O~(n6)O~(n3)

Joe Bebel
sumber
komplemen (kekompakan) bahkan lebih mudah untuk disaksikan!
Yonatan 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(n2ϵ)

Dengan kata lain, SETH memberi kita masalah alami dalam dengan kesenjangan antara menemukan dan memverifikasi. Ω ( n 1 - ϵ )PΩ(n1ϵ)

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(n2/logn)

SamM
sumber