NP-твердость подразумевает P-твердость?

Если проблема является NP-сложной (с использованием полиномиального сокращения времени), означает ли это, что она является P-сложной (с использованием пространства журнала или сокращений NC)? Кажется интуитивно понятным, что если это так же сложно, как любая проблема в NP, то это должно быть так же сложно, как и любая проблема в P, но я не вижу, как связать сокращения и получить сокращение пространства журнала (или NC).

cc.complexity-theory np-hardness Адам Крум
источник

Это имеет место , если вы используете один и тот же вид сокращений для обеих сторон, например,

проблема WRT сокращения лог-пространства также

сокращения WRT лог-пространства.

N P - h a r d

$\mathbf{NP-hard}$

P - h a r d

$\mathbf{P-hard}$

Каве

т. е. ваша интуиция верна, но вопрос, который вы задали, требует большего (поскольку вы используете различные виды сокращения).

Каве

Самая важная часть вопроса - какие понятия сводимости вы используете, но эта информация каким-то образом заключена в скобки, как будто это наименее важная информация!

Цуёси Ито

Ответы:

Никаких таких последствий не известно. В частности, может быть так, что в этом случае все проблемы (включая тривиальные) являются NP-трудными при сокращениях за многократное время (поскольку сокращение может просто решить проблему), но тривиальные (в частности, те, которые лежат в L), конечно, не P-hard при сокращении пространства журналов (как в противном случае L = P). $L \ne P = NP$

То же самое касается NC вместо L.

Ноам
источник

Большое спасибо за этот ответ. Я думаю, что для многих людей - и, по крайней мере, для меня - этот вопрос казался несущественным, но после прочтения вашего ответа на три предложения он «очевидно» глубок. (Также, спасибо за вопрос, @ Адам Крум.)

Аарон Стерлинг