Masalah NP-lengkap dengan banyak polinomially sertifikat?

Mari kita sebut bahasa NP yang jarang memiliki sertifikat jika dan hanya jika: $L \in$

Ada polinomial sedemikian rupa sehingga untuk setiap input ukuran , jika maka set sertifikat yang memverifikasi bahwa berukuran polinomially, yaitu . $p : \mathbb{N} \rightarrow \mathbb{N}$ $x \in \Sigma^*$ $n$ $x \in L$ $U_x$ $u$ $x \in L$ $|U_x| \leq p(n)$

Dalam istilah yang lebih pendek, setiap masukan memiliki pada jumlah yang paling polinomial sertifikat yang memverifikasi dimasukkan dalam . $x$ $L$

Contoh: Untuk mengilustrasikan, pertimbangkan masalah : $\mathbf{CLIQUE}$

$\mathbf{CLIQUE} = \{\; (G,k) \;\mid\; G \text{ has a clique of size } k \;\}$

Bahasa yang tidak jarang sertifikat , sebagai masukan bisa dengan mudah memiliki jumlah eksponensial -cliques bertindak sebagai sertifikat yang membuktikan bahwa . $\mathbf{CLIQUE}$ $x = (G,k)$ $k$ $x \in \mathbf{CLIQUE}$

Contoh Akhir

Pertanyaannya adalah, adakah: apakah ada bahasa lengkap NP-isian yang diketahui jarang? Wawasan apa pun dipersilakan, bahkan jika mereka tidak menjawab pertanyaan!

Catatan : definisi ini berbeda dari bahasa yang jarang!

cc.complexity-theory complexity-classes gdiazc
sumber

Yang pasti saya mengerti, apakah ini benar?

secara teknis didefinisikan sehubungan dengan beberapa verifier

tertentu , yaitu, untuk

. Dan

adalah "jarang sertifikat" jika dan hanya jika terdapat verifier

untuk

seperti itu yang

s memenuhi kondisi polinomial-ukuran.

U_{x}

$U_x$

V

$V$

x \in L

$x \in L$

U_{x} = {u : V (x, u) = 1}

$U_x = \{u : V(x,u) = 1\}$

L

$L$

V

$V$

L

$L$

U_{x}

$U_x$

usul

Jawaban:

Tidak, tidak ada bahasa lengkap yang dikenal dengan sertifikasi jarang . Kelas yang Anda gambarkan dikenal sebagai . Hal ini secara luas diyakini bahwa , Jadi, ada masalah -Lengkap dikenal di fewP. (Tidak mungkin kecuali ). $NP$ $fewP$ $fewP \ne NP$ $NP$ $fewP=NP$

Mohammad Al-Turkistany
sumber

Inilah yang saya cari. Bersulang!

gdiazc

Saya telah menemukan referensi untuk beberapa P (di Kebun Binatang Kompleksitas), tetapi apakah Anda memiliki referensi untuk mendukung pernyataan: "secara luas diyakini bahwa beberapa P

NP"? Sebagai contoh, akankah beberapa P

NP menyiratkan

atau semacamnya?

\neq

$\neq$

=

$=$

P = N P

$P = NP$

gdiazc

@ PayfunPay: Saya cukup yakin dia berbicara tentang

dan bukan

bersifat lebih umum - ia mensyaratkan paling banyak sertifikat polinomi diterima oleh verifier, tetapi apakah

atau tidak tidak ditentukan oleh apakah ada sertifikat yang diterima oleh verifier, tetapi lebih merupakan predikat tambahan

. OQ tampaknya bermaksud untuk bertanya tentang keberadaan keberadaan sertifikat apa pun yang menyiratkan

F e w P

$\mathsf{FewP}$

F e w

$\mathsf{Few}$

F e w

$\mathsf{Few}$

x \in L

$x \in L$

Q (x, | U_{x} |)

$Q(x, |U_x|)$

x \in L

$x \in L$ , Yang persis

F e w P

$\mathsf{FewP}$

Joshua Grochow

@TayfunPay: Sejauh yang saya mengerti,

dan

yang kedua kelas semantik, seperti

atau

. Secara khusus, apa yang Anda katakan tidak benar.

, seperti halnya

, mensyaratkan bahwa jumlah jalur penerimaan verifier dibatasi oleh polinomial pada semua input. (Apa yang Anda tetapkan adalah sesuatu seperti

atau

F e w

$\mathsf{Few}$

F e w P

$\mathsf{FewP}$

U P

$\mathsf{UP}$

B P P

$\mathsf{BPP}$

F e w

$\mathsf{Few}$

F e w P

$\mathsf{FewP}$

P r o m i s e F e w

$\mathsf{PromiseFew}$

...) Lihat Def. 1.2 dari Cai & Hemachandra:dx.doi.org/10.1007/BFb0028987

P r o m i s e F e w P

$\mathsf{PromiseFewP}$

Joshua Grochow

@ JoshuaGrochow Saya baru saja mendapat kesempatan untuk melihatnya. Anda benar,

memang kelas semantik. Saya berpikir bahwa itu adalah versi sintaksis dari

. OK Namun, saya masih percaya kuesioner menanyakan jenis skenario "jika dan hanya jika". Karena bahasa yang diberikan

adalah dalam

"jika" jumlah total jalur penerima dibatasi oleh polinomial dan "tidak" dalam

jika tidak ada jalur penerimaan. Jadi kita TIDAK tahu apa yang terjadi ketika jumlah jalur penerimaan bersifat eksponensial karena itu bukan "jika dan hanya jika" ....

F e w

${\bf Few}$

F e w P

${\bf FewP}$

L

$L$

F e w P

${\bf FewP}$

F e w P

${\bf FewP}$

Tayfun Membayar