Apakah NP = coNP menyiratkan P = NP?

8

Kita tahu bahwa P = NP menyiratkan NP = coNP. Apakah implikasi sebaliknya berlaku? Apakah NP sama dengan BNP menyiratkan bahwa P sama dengan NP? Jika tidak, mengapa tidak?

Saya mencari di Google tetapi tidak menemukan jawabannya.

James Johnson
sumber

Jawaban:

6

Kasus yang memungkinkan adalah mungkin. Alasan mengapa menyiratkan adalah bahwa ditutup di bawah komplemen, dan jadi jika , harus ditutup di bawah komplemen juga.PNP=coNPP=NPNP=coNPPP=NPNP

Kelas yang ditutup dengan komplemen tidak selalu menyiratkan apa pun tentang mitra deterministiknya. Sebagai contoh, kita tahu bahwa ditutup di bawah komplemen, tetapi tidak tahu apakah .NLL=NL

Mike B.
sumber