Konsekuensi dari

Saya memiliki bagian dari upaya pembuktian $\oplus \mathbf{P} \subseteq \mathbf{NP}$ . Upaya pembuktian terdiri dari pengurangan Karp dari $\oplus \mathbf{P}$ masalah lengkap $\oplus$ 3-REGULER VERTEX COVER ke SAT.

Diberikan grafik kubik $G$ , reduksi menghasilkan rumus CNF $F$ memiliki kedua properti berikut:

$F$ memiliki paling banyak $1$ tugas yang memuaskan.
memuaskan jika dan hanya jika jumlah simpul penutup adalah ganjil. $F$ $G$

Pertanyaan

Yang akan menjadi konsekuensi dari ? Konsekuensi yang saya sudah sadari adalah sebagai berikut: akan dapat direduksi menjadi melalui reduksi acak dua sisi. Dengan kata lain kita akan memiliki (menggunakan Teorema Toda, yang menyatakan bahwa , dengan hanya mengganti dengan ). Saya tidak tahu apakah $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\mathbf{PH}$ $\mathbf{NP}$ $\mathbf{PH}\subseteq\mathbf{BPP}^{\mathbf{NP}}$ $\mathbf{PH}\subseteq\mathbf{BPP}^{\oplus\mathbf{P}}$ $\oplus\mathbf{P}$ $\mathbf{NP}$ $\mathbf{BPP}^{\mathbf{NP}}$ telah terbukti terkandung dalam beberapa tingkat dari Hirarki Polinomial: jika ya, konsekuensi lebih lanjut adalah bahwa runtuh ke tingkat . ~~Selain itu, di bawah asumsi derandomisasi yang diterima secara luas (~~ ~~), Hirarki Polinomial akan runtuh antara tingkat pertama dan kedua, karena kita akan memiliki~~ ~~(saya diberitahu ini bukan benar, namun saya tidak akan menghapus baris ini sampai saya sepenuhnya mengerti mengapa).~~ $i$ $\mathbf{PH}$ $i$ ~~$\mathbf{BPP} = \mathbf{P}$ $\mathbf{PH} = \mathbf{P}^\mathbf{NP} = \Delta_2^\mathbf{P}$~~

Jika saya tidak salah, pengurangan tersebut akan benar-benar membuktikan lebih dari . Ini akan membuktikan . Yang akan menjadi konsekuensi dari , selain yang sudah tersirat oleh ? Saya tidak tahu persis apakah akan menambah kejutan pada konsekuensi yang sudah mengejutkan dari $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{NP}$ , atau sejauh mana. Secara intuitif saya kira itu akan, dan sampai batas yang cukup luas.

cc.complexity-theory graph-theory complexity-classes sat counting-complexity Giorgio Camerani
sumber

ditutup di bawah komplemen, dan reduksi PH secara acak menjadi

adalah banyak-satu, maka

sebenarnya menyiratkan

, dan

\oplus P

$\oplus\mathrm P$

\oplus P

$\oplus\mathrm P$

\oplus P \subseteq N P

$\oplus\mathrm P\subseteq\mathrm{NP}$

P H = Σ_{2}^{P} = Π_{2}^{P} = A M \cap c o A M

$\mathrm{PH}=\Sigma^P_2=\Pi^P_2=\mathrm{AM}\cap\mathrm{coAM}$

P H \subseteq N P / p o l y \cap c o N P / p o l y

$\mathrm{PH}\subseteq\mathrm{NP/poly}\cap\mathrm{coNP/poly}$ . UP tidak membuat banyak perbedaan (lih. Kurangnya apa pun yang berguna di cstheory.stackexchange.com/questions/3887 ).

Emil Jeřábek

@ EmilJeřábek Terima kasih atas komentar Anda yang menarik, saya tidak tahu konsekuensinya. Aku tahu pertanyaan Anda menunjuk saya untuk, namun saya akan diharapkan

(serta

) menjadi mengejutkan, setidaknya karena

tidak diketahui memiliki masalah lengkap. Sangat menarik bagaimana sesuatu yang diduga secara luas salah (

) tidak diketahui memiliki, jika benar, konsekuensi yang mengejutkan. Anda dapat mempertimbangkan untuk memperluas komentar Anda menjadi sebuah jawaban ...

\oplus P \subseteq U P

$\oplus \mathbf{P}\subseteq\mathbf{UP}$

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$

U P

$\mathbf{UP}$

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$

Giorgio Camerani

Tidak, Anda salah besar. BPP = P hanya mengatakan bahwa setiap bahasa yang dapat dihitung oleh mesin BPP juga dapat dihitung oleh mesin P. Itu tidak mengatakan apa pun tentang bahasa yang dapat dihitung oleh mesin BPP dengan oracle nontrivial. Dengan argumen Anda yang salah, NP = P menyiratkan

untuk setiap

, yang kami tahu salah, maka

terpecahkan. Dan untuk hal ini, argumen Anda akan menyiratkan

, karena ada ada firman

yang

{N P}^{A} = P^{A}

$\mathrm{NP}^A=\mathrm P^A$

A

$A$

N P \neq P

$\mathrm{NP}\ne\mathrm P$

B P P \neq P

$\mathrm{BPP}\ne\mathrm P$

A

$A$

{B P P}^{A} \neq P^{A}

$\mathrm{BPP}^A\ne\mathrm P^A$ .

Emil Jeřábek

@Iorgio: Dia hanya mengklaim bahwa garis penalaran yang Anda anggap tidak bekerja dalam situasi ini. Bagian yang relevan: "Jika mesin yang saya pasang oracle setidaknya sekuat, mengapa inklusi tidak diikuti?". Dia tampaknya tidak mengatakan bahwa klaim itu sendiri salah; Hanya saja intuisi khusus Anda tidak berfungsi. Kami belum bisa mengesampingkan bahwa aspek probabilistik dari PPTM tidak bisa mendapatkan lebih banyak manfaat dari ramalan itu. Probabilistic TM memiliki lebih banyak alat yang dapat digunakan, tetapi alat tersebut mungkin tidak memberikan manfaat yang ketat tanpa yang tambahan (seperti ramalan NP).

mdxn

Bahkan dengan asumsi bahwa PRNG cukup kuat untuk meruntuhkan P dan BPP ada, saya tidak melihat mengapa ini harus berarti BPP dengan oracle NP dan P dengan oracle NP harus sama. Biasanya PRNG memiliki jaminan bahwa tidak ada sirkuit poliasze yang dapat membedakan outputnya dari bit yang benar-benar acak. Tetapi untuk mesin oracle Anda membutuhkan jaminan untuk setiap sirkuit polsize dengan gerbang NP diizinkan, dan ini lebih kuat. Impagliazzo-Wigderson memang merelatifikasi, tetapi Anda perlu memperkuat asumsi kekerasan ( eccc.hpi-web.de/report/1998/055/comment/1/download )

Sasho Nikolov

Konsekuensi dari

Jawaban: