Отличается ли

Можем ли мы доказать, что для любого языка который не является трудным (предполагается, что ), ? С другой стороны, это может быть доказано при любых разумных предположениях? $L\in\mathsf{NP}$ $\mathsf{NP}$ $\mathsf P \ne \mathsf{NP}$ $\mathsf{P}^L \ne \mathsf{P}^{\text{SAT}}$

cc.complexity-theory complexity-classes np-intermediate GMB
источник

Я думаю , что этот вопрос имеет глупый ответ: Пусть

, то , конечно ,

когда вы предполагаете , что

. Таким образом, вы можете захотеть, все еще предполагая, что

находится в

а не в

-hard. [Редактировать: О, я прочитал ваш комментарий ниже, поэтому ваш вопрос, похоже, звучит так: «Правда ли, что для всех таких

место неравенство?», А не «Существует ли такой

L \in P \subseteq N P

$L\in\mathsf P\subseteq\mathsf{NP}$

P^{L} \neq P^{SAT}

$\mathsf P^L\neq \mathsf P^{\text{SAT}}$

P \neq N P

$\mathsf P\neq\mathsf{NP}$

P \neq N P

$\mathsf P\neq\mathsf{NP}$

L

$L$

N P ∖ P

$\mathsf{NP}\setminus\mathsf P$

N P

$\mathsf{NP}$

L

$L$

L

$L$ ? "=> Я редактирую ваш вопрос!]

Бруно,

Ответы:

Зависит от вашего определения NPI. Если А является неполным для тьюринговых, ответ да , так как СБ не в . $P^A$

Если A просто много-один неполно, то мы не знаем, как это доказать. У нас есть релятивизированный мир с множеством A в NP, так что A не является NP-полным с помощью сокращений много-один, но SAT можно вычислить одним запросом к A. (Теорема 1.9 в этой статье ).

Лэнс Фортноу
источник

Вы имеете в виду теорему 1.9?

Джеффри Ирвинг

Вы правы. Исправлена.

Лэнс Фортноу