Если

10

Если P=NP , то есть L=NL ? Я задаю этот вопрос, потому что для других недетерминированных классов кажется, что P=NP всегда устанавливает, что они равны своим детерминированным аналогам.

TTR
источник

Ответы:

15

Это открытый вопрос исследования. В нашем текущем состоянии знаний, зная , не будет ни подразумевают L = N L , ни LN L . И, наоборот, знание L = N L или LN L ничего бы не значило в вопросе P против N P. (Но возможно , что доказательство из L против N L сказал бы нам что - нибудь о P против N PP=NPL=NLLNLL=NLLNLPNPLNLPNP или наоборот.)

Мы знаем , что , где равенство следует из теоремы Савича в . Недетерминированный вариант теоремы о пространственной иерархии гласит, что N LN P S P A C ELNLPNPPSPACE=NPSPACENLNPSPACEпоэтому мы знаем, что по крайней мере одно из установленных включений должно быть строгим. Мы вроде думаю , что все они строги , но наши нынешние знания не исключает любое подмножество из них, до тех пор , как она включает в себя по меньшей мере один между и P S P A C E .NLPSPACE

Дэвид Ричерби
источник