Implikasi antara dan ?

Jika kita dapat membuktikan bahwa , apakah itu menyiratkan bahwa ? $\mathsf{L}=\mathsf{P}$ $\mathsf{NL}=\mathsf{NP}$

Saya pikir itu masalahnya, tapi saya tidak bisa membuktikannya (juga untuk yang sebaliknya).

cc.complexity-theory complexity-classes nondeterminism Thatchaphol
sumber

Membuktikan kebalikannya akan sangat sulit ...

domotorp

Kebalikannya bermuara pada apakah NL = P menyiratkan L = P. Ini tidak selalu benar kecuali L = NL.

Mohammad Al-Turkistany

Saya memposting pertanyaan terkait tentang hubungan antara P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L. Jika Anda tertarik, silakan melihatnya. Terima kasih! cstheory.stackexchange.com/questions/31073/...

Michael Wehar

Jawaban:

Tidak. Mungkin L = P dan P! = NP yang menyiratkan bahwa NL! = NP karena NL terkandung dalam P.

Mohammad Al-Turkistany
sumber

Saya pikir mungkin akan bermanfaat, daripada hanya menyatakan ini secara langsung, untuk memberikan intuisi bagaimana ini bisa terjadi. Mempertimbangkan konstruksi NP = ∃P (yaitu definisinya dalam hal memeriksa saksi menggunakan algoritma polytime), saya dapat melihat bagaimana orang dapat menebak bahwa jika P = L , kita dapat dengan mudah mendapatkan NP = ∃L = NL dengan substitusi. Mungkin beberapa komentar tentang bagaimana batasan logaritmik pada pita kerja akan membantu untuk menunjukkan mengapa ini tidak terjadi.

Niel de Beaudrap