Akankah menyiratkan ?

10

Jika maka hierarki runtuh ke level kedua (oleh teorema Karp-Lipton). Tetapi bagaimana dengan dan ? $\sf RP = NP$ $\sf NP$ $\sf coNP$

Saya mencoba membuktikan bahwa terkandung dalam (arah lainnya sepele jika ) tetapi tidak berhasil, dan saya bahkan tidak yakin itu benar. $\sf BPP$ $\sf NP$ $\sf RP = NP$

Bagaimana menurut anda?

complexity-theory complexity-classes probabilistic-algorithms Robert777
sumber

Saya tidak berpikir ada alasan formal tertentu untuk berpikir demikian (tetapi tidak ada alasan untuk tidak melakukannya). Singkatnya, saya percaya itu terbuka.

Luke Mathieson

Membuktikan tanpa syarat adalah masalah terbuka.

B P P \subseteq N P

$\mathbb{BPP} \subseteq \mathbb{NP}$

chazisop

3

Jika kita dapat membuktikan bahwa RP ditutup di bawah komplemen maka kita dapat mengatakan bahwa Jika RP = NP maka itu menyiratkan NP = Co-NP.

Tetapi kita tidak tahu apakah RP = Co-RP atau tidak. BPP = P dapat dibuktikan dengan beberapa asumsi yang masuk akal tetapi RP BPP. $\subseteq$

Jika kami menunjukkan RP = BPP maka pernyataan Anda akan benar.

Referensi:

Pragya
sumber

atau RP = ZPP.

1

Gunakan di Cook dan Krajicek, Konsekuensi dari provabilitas NP P / poly (Jurnal Logika Simbolik, 72 (4): 1353-71 , 2007; PS ). $\mathsf{RP=NP\implies NP\subseteq P/poly}$ $\,\subseteq\,$

T ....
sumber

Akankah menyiratkan ?

Jawaban: