Apakah ada tugas yang dapat dipecahkan dalam waktu polinomial tetapi tidak dapat diverifikasi dalam waktu polinomial?

Seorang kolega saya dan saya baru saja menekan beberapa catatan dari salah satu profesor kami. Catatan menyatakan bahwa ada tugas-tugas yang mungkin diselesaikan dalam waktu polinomial (berada dalam kelas PF) tetapi yang TIDAK dapat diverifikasi dalam waktu polinomial (TIDAK dalam kelas NPF).

Untuk menguraikan tentang kelas-kelas ini: Kami mendapatkan beberapa input X dan menghasilkan beberapa output Y sedemikian rupa sehingga (X, Y) berhubungan dengan R yang mewakili tugas kami. Jika dimungkinkan untuk mendapatkan Y untuk X dalam waktu polinomial, tugas itu termasuk kelas PF. Jika dimungkinkan untuk memverifikasi sertifikat panjang polinomial Z yang membuktikan tupel (X, Y) dalam kaitannya dengan R dalam waktu polinomial, maka tugas tersebut termasuk dalam kelas NPF.

Kami tidak berbicara tentang masalah keputusan, di mana jawabannya hanya YA atau TIDAK (lebih formal jika beberapa string milik beberapa bahasa). Untuk masalah keputusan, tampaknya PF adalah subset NPF yang tepat. Namun, untuk tugas lain mungkin berbeda.

Apakah Anda mengetahui tugas yang dapat diselesaikan dalam waktu polinomial tetapi tidak diverifikasi dalam waktu polinomial?

complexity-theory np Drozi
sumber

Mungkin saya salah paham, tetapi mengapa berikut ini bukan algoritma verifikasi polinomial-waktu? Diberikan , hitung sendiri fungsi , menggunakan algoritma polinomial-waktu, dan kembalikan "benar" jika . Mungkinkah Anda salah membaca atau profesor salah bicara dan sebaliknya bermaksud mengatakan bahwa ada masalah yang dapat diverifikasi dalam waktu polinomial tetapi tidak dapat dipecahkan dalam waktu polinomial?

(x, y)

$(x,y)$

f (x)

$f(x)$

f (x) = y

$f(x)=y$

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen "untuk mengatakan bahwa ada masalah yang dapat diverifikasi dalam waktu polinomial tetapi tidak dapat dipecahkan dalam waktu polinomial?" [ref. dibutuhkan]

T. Verron

@ T. Verron Haha ya, saya juga akan sangat senang melihat bukti profesor untuk klaim ini;)

Lieuwe Vinkhuijzen

Jawaban:

Ini hanya mungkin jika ada banyak keluaran yang dapat diterima untuk input yang diberikan. Yaitu, ketika hubungan bukan fungsi karena melanggar keunikan. $R$

Misalnya, pertimbangkan masalah ini:

Diberikan (diwakili dalam unary) dan TM , menghasilkan TM lainnya sehingga $n \in \mathbb{N}$ $M$ $N$ $L(M)=L(N)$ dan (di mana adalah singkatan dari penyandian (nomor Gödel ) dari menjadi bilangan asli) $\# N > n$ $\# N$ $N$

Memecahkan ini sepele: terus tambahkan beberapa status redundan ke TM , mungkin dengan beberapa transisi dummy di antara mereka, sampai pengkodeannya melebihi . Ini adalah aplikasi dasar yang diulang dari Padding Lemma pada TM. Ini akan membutuhkan bantalan, yang masing-masing dapat menambahkan satu negara, maka itu dapat dilakukan dalam waktu polinomial. $M$ $n$ $n$

Di sisi lain, mengingat adalah diputuskan untuk memeriksa apakah adalah output yang benar untuk input . Memang, memeriksa tidak dapat ditentukan (menerapkan teorema Padi), dan kendala hanya membuang banyak dari mereka secara terbatas . Karena kami menghapus sejumlah elemen hingga dari masalah yang tidak dapat ditentukan, kami masih mendapatkan masalah yang tidak dapat ditentukan. $n,M,N$ $N$ $n,M$ $L(M)=L(N)$ $\#N > n$ $N$

Anda juga dapat mengganti properti yang tidak dapat ditentukan untuk mendapatkan variasi yang masih dapat dihitung tetapi NP sulit / lengkap. Misalkan diberikan (dalam unary) itu sepele untuk menghitung grafik memiliki -clique di dalamnya. Tetapi mengingat sulit untuk memeriksa apakah -clique ada. $L(M)=L(N)$ $n$ $G$ $n$ $n,G$ $n$

chi
sumber

Diharapkan ini tidak menjadi masalah. Jawaban bagus!

Filip Haglund

Ini tidak menjawab pertanyaan. OP secara khusus meminta masalah yang tidak dapat diverifikasi dalam arti biasa, di mana, selain input dan jawaban yang diduga, kami mendapatkan sertifikat

yang menyatakan kebenaran jawaban tersebut. Dalam kasus Anda, sertifikat adalah bit yang digunakan untuk secara nondeterministis menghasilkan Mesin Turing setara baru. Mengingat

dan

, mudah untuk memeriksa apakah

memberikan mesin

. Tanpa

, pertanyaannya adalah apakah mudah untuk menghasilkan contoh instans dari bahasa (NPC), yang hanya berlaku di Minicrypt dan Cryptomania.

z

$z$

M, N

$M, N$

z

$z$

z

$z$

M

$M$

z

$z$

Lieuwe Vinkhuijzen

@chi Tidak semua pasangan

dapat disertifikasi, tetapi pasangan

dihasilkan oleh algoritme Anda dapat disertifikasi. Sertifikat adalah transkrip algoritma Anda yang menghasilkan

dari

(mis. "Mulai dengan

, lalu tambahkan status ini, dan tambahkan transisi ini, lalu ... dan voilà,

!"). Secara umum, jika

adalah algoritma nondeterministic yang, diberikan

, selalu menghitung

dapat diterima , maka transkrip dari jalur komputasi

adalah sertifikat yang diberikan

dapat diterima.

M, N

$M, N$

M, N

$M, N$

N

$N$

M

$M$

M

$M$

N

$N$

T

$T$

x

$x$

y

$y$

T (x)

$T(x)$

y

$y$

Lieuwe Vinkhuijzen

@ Ya Ada sedikit nuansa dalam pertanyaan: Untuk hubungan arbitrer

, ada kemungkinan bahwa tidak semua

dapat diterima dapat disertifikasi, dan Anda memberikan contoh yang elegan. Namun, pertanyaannya tidak menanyakan apakah ada hubungan yang dapat diterima tetapi tidak dapat disertifikasi (jawabannya adalah ya , dengan contoh Anda), melainkan menanyakan apakah kita dapat memiliki algoritme yang menghasilkan keluaran yang dapat diterima dan tidak dapat disertifikasi. Jawabannya, di sini, harus tidak , karena argumen di atas.

R

$R$

y

$y$

Lieuwe Vinkhuijzen

@ Ya, saya tidak tahu apa yang ingin ditanyakan oleh OP, tapi saya menemukan jawaban Anda sangat jelas, saya belajar sesuatu! imo pertanyaannya dapat dibaca dengan cara Anda lakukan, atau sama masuk akal sebagai " apakah fungsi satu arah ada? " (mungkin) atau " adalah contoh sulit dari masalah NP mudah untuk menghasilkan? " (Saya harap demikian untuk RSA), atau, cara saya membacanya, sebagai " Is ? $NP\subsetneq P$ " (no).

Lieuwe Vinkhuijzen

Ini hanyalah penjabaran dari kalimat pertama dari jawaban @ chi, karena saya tidak menemukannya dengan jelas.

Idenya adalah, jika Anda memiliki algoritma yang menemukan jawaban untuk beberapa masalah dalam waktu polinomial, maka ada dua kemungkinan:

Anda sebelumnya telah membuktikan (secara matematis) bahwa output algoritma adalah solusi untuk masalah, dalam hal ini, langkah-langkah algoritma itu sendiri membentuk bukti kebenaran.
Anda memiliki algoritme yang berbeda untuk memeriksa bahwa output memang merupakan solusi, dalam hal ini Anda harus menjalankan algoritme ini (jika tidak, Anda akan jatuh dalam kasus # 1), yang menyiratkan Anda melakukannya dalam waktu polinomial.

Karena itu, tidak ada masalah seperti itu.

Mehrdad
sumber

Saya tidak mengerti # 2. Apa yang menyiratkan bahwa algoritma yang berbeda berjalan dalam waktu polinomial?

Albert Hendriks

@AlbertHendriks: Jika verifier tidak berjalan dalam waktu polinomial maka pemecah asli tidak bisa mengklaim telah menemukan solusi yang benar dalam waktu polinomial, karena itu perlu menjalankan verifier untuk memastikan solusinya benar.

Mehrdad