Superset waktu dari bahasa lengkap NP dengan banyak sekali string dikecualikan darinya

Untuk setiap bahasa lengkap NP yang sewenang-wenang, adakah selalu superset polytime yang komplemennya juga tidak terbatas?

Versi sepele yang tidak menetapkan superset memiliki pelengkap tak terbatas telah diminta di /cs//q/50123/42961

Untuk keperluan pertanyaan ini, Anda dapat mengasumsikan bahwa . Seperti yang dijelaskan Vor, jika maka jawabannya adalah "Tidak". (Jika , maka adalah NP-complete. Jelas tidak ada superset dari yang tidak terbatas dan memiliki yang tak terbatas komplemen, karena komplemen hanya memiliki satu elemen.) Dengan demikian kita dapat fokus pada case . $P \ne NP$ $P = NP$ $P = NP$ $X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$ $X$ $X$ $P \ne NP$

cc.complexity-theory np-complete structural-complexity ARi
sumber

Jika

P = N P

$P = NP$ maka

adalah NP-complete. Jelas tidak ada superset dari

yang tak terbatas dan memiliki komplemen tak terbatas (perhatikan bahwa ). Jadi Anda bisa "fokus" pada apa yang terjadi jika .

X = {x ∣ x \in N^{+} \land x > 1}

$X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$

X

$X$

\bar{X} = {1}

$\bar{X} = \{1\}$

P \neq N P

$P \neq NP$

Marzio De Biasi

Bagaimana dengan versi yang direlatifikasi: Apakah ada oracle

semua set co-NP

adalah P

imun.

A

$A$

^{A}

$^A$

^{A}

$^A$

Lance Fortnow

@LanceFortnow ... atau untuk bahasa lengkap apa pun pada khususnya. Kelas kompleksitas, selalu ada superset non trivial dengan kompleksitas yang lebih rendah.

ARi

Jawaban:

Setiap set -Lengkap berisi subset tak terbatas dalam dengan asumsi bahwa $\mathsf{coNP}$ $\mathsf{P}$

generator pseudorandom ada, dan
ada permutasi satu arah yang aman.

Dengan kata lain, dengan asumsi bahwa dua dugaan ini benar, tidak ada set -Lengkap adalah P kekebalan tubuh . Sebagaimana ditunjukkan dalam komentar oleh Lance, ini tersirat oleh Teorema 4.4 of $\mathsf{coNP}$

Glasser, Pavan, Selman, dan Sengupta, " Properti set NP-complete ", SIAM J. Comput. 36 (2), 516–542.

(Kaveh telah menunjukkan bahwa pertanyaan Anda adalah setara dengan apakah setiap set -Lengkap berisi terbatas bagian. Dalam bahasa lain, ini mengatakan bahwa tidak ada -Lengkap set " -immune." Ini adalah bahasa yang digunakan dalam teorema yang dirujuk di atas.) $\mathsf{coNP}$ $\mathsf{P}$ $\mathsf{coNP}$ $\mathsf{P}$

Joshua Grochow
sumber

Draf ECCC

Kaveh

Dengan fungsi hard-core yang kuat (dan iterasi ), permutasi satu arah menyiratkan generator pseudorandom.

@ RickyDemer: Lihat Definisi 4.1-4.3 dalam makalah yang dikutip. Jika saya memahami dengan benar, OWP menyiratkan apa yang mereka sebut "crypto-PRGs", tetapi belum tentu apa yang mereka sebut "PRGs" di surat kabar Glasser-Pavan-Selman-Sengupta. Untuk hasilnya, mereka (tampaknya) membutuhkan OWP dan apa yang mereka sebut PRG.

Joshua Grochow

Kaveh hanya menunjukkan kesetaraan dengan set co-NP-lengkap adalah P-imun, tetapi kesimpulan dari teorema 4.4 dalam Glasser et al bahwa semua set NP-lengkap harus memiliki pengurangan panjang yang meningkat, juga menyiratkan bahwa tidak ada co-NP- set kekebalan-P lengkap.

Lance Fortnow

@ JoshuaGrochow Terima kasih ... tetapi adakah asumsi yang bisa kita buat yang pada gilirannya menyiratkan tidak adanya bahasa seperti itu. Saya lebih tertarik pada skenario di mana tidak ada superset waktu poli

ARi

Pertanyaan menarik. Pernyataan

untuk setiap NP-lengkap , ada dalam P sehingga dan tidak terbatas. $L$ $U$ $L \subseteq U$ $U^c$

setara dengan:

untuk setiap NP-complete , komplemen berisi set P yang tak terbatas. $L$ $L$

yang pada gilirannya setara dengan

setiap set coNP-complete berisi set P yang tak terbatas.

~~yang secara simetri sama dengan~~

~~setiap set NP-lengkap berisi set-P yang tak terbatas.~~

~~Saya kira jawabannya tidak diketahui. Saya pikir set NP-lengkap alami memenuhi kondisi ini dengan mudah. Saya tidak berpikir kita memiliki alat untuk membangun set buatan yang gagal pernyataan itu.~~ (lihat komentar Lance di bawah)

Kaveh
sumber

Pernyataan awal Anda sepele benar. (Misalkan U bahasa penuh.)

Ini merupakan rangkaian pemotongan yang menarik ... Bisakah Anda memberikan contoh bahasa lengkap NP alami dalam hal ini

ARi

Simetri tidak masuk akal. Sebagai contoh, setiap set ce memiliki himpunan bagian komputer yang tak terbatas tetapi ada set co-ce yang tidak.

Lance Fortnow