Последствия между и ?

Если мы можем доказать, что , означает ли это, что ? $\mathsf{L}=\mathsf{P}$ $\mathsf{NL}=\mathsf{NP}$

Я думал, что это так, но я не могу доказать это (также для обратного).

cc.complexity-theory complexity-classes nondeterminism Thatchaphol
источник

Доказать обратное было бы довольно сложно ...

domotorp

Обратное утверждение сводится к тому, подразумевает ли NL = P L = P. Это не обязательно верно, если L = NL.

Мухаммед Аль-Туркистани

Я опубликовал соответствующий вопрос об отношениях между P против L, NP против NL, BPP против BPL, ⊕P против ⊕L. Если вы заинтересованы, пожалуйста, не стесняйтесь взглянуть. Спасибо! cstheory.stackexchange.com/questions/31073/…

Майкл Вехар

Ответы:

Нет. Возможно, что L = P и P! = NP, что означает, что NL! = NP, поскольку NL содержится в P.

Мухаммед Аль-Туркистани
источник

Я думаю, что было бы полезно, а не просто прямо заявить об этом, чтобы дать некоторую интуицию, как это могло бы быть. Рассматривая конструкцию NP = ∃P (т. Е. Ее определение в терминах проверки свидетеля с использованием алгоритма многократного использования), я могу видеть, как можно догадаться, что если P = L , то мы могли бы просто получить NP = ∃L = NL путем подстановки. Возможно, некоторые замечания о том, как логарифмическое ограничение на рабочей ленте поможет указать, почему это не так.

Ниль де Бодрап