Если , то есть ? Я задаю этот вопрос, потому что для других недетерминированных классов кажется, что всегда устанавливает, что они равны своим детерминированным аналогам.
Если , то есть ? Я задаю этот вопрос, потому что для других недетерминированных классов кажется, что всегда устанавливает, что они равны своим детерминированным аналогам.
Это открытый вопрос исследования. В нашем текущем состоянии знаний, зная , не будет ни подразумевают L = N L , ни L ≠ N L . И, наоборот, знание L = N L или L ≠ N L ничего бы не значило в вопросе P против N P. (Но возможно , что доказательство из L против N L сказал бы нам что - нибудь о P против N P или наоборот.)
Мы знаем , что , где равенство следует из теоремы Савича в . Недетерминированный вариант теоремы о пространственной иерархии гласит, что N L ≠ N P S P A C Eпоэтому мы знаем, что по крайней мере одно из установленных включений должно быть строгим. Мы вроде думаю , что все они строги , но наши нынешние знания не исключает любое подмножество из них, до тех пор , как она включает в себя по меньшей мере один между и P S P A C E .