Естественные кандидаты на иерархию внутри NPI

Предположим , что $\mathsf{P} \neq \mathsf{NP}$ . $\mathsf{NPI}$ - класс задач в $\mathsf{NP}$ которых нет ни в $\mathsf{P}$ ни в $\mathsf{NP}$ -твердых. Вы можете найти список проблем предположительно $\mathsf{NPI}$ здесь .

Теорема Ладнера говорит нам, что если то существует бесконечная иерархия задач , то есть существуют проблемы которые сложнее, чем другие проблемы.Н П И Н П И Н П $\mathsf{NP}\neq\mathsf{P}$$\mathsf{NPI}$$\mathsf{NPI}$$\mathsf{NPI}$

Я ищу кандидатов на такие задачи, т.е. меня интересуют пары задач
- , - и предполагаются как , - известно , что сводится к , - но нет никаких известных сокращений от к . A B N P I A B B $A,B \in \mathsf{NP}$
$A$$B$$\mathsf{NPI}$
$A$$B$
$B$$A$

Еще лучше, если есть аргументы в поддержку этого, например, есть результаты, которые не сводит к предполагая некоторые предположения в теории сложности или криптографии.$B$$A$

Есть ли естественные примеры таких проблем?

Пример. Предполагается, что проблема изоморфизма графов и проблема целочисленной факторизации находятся в и существуют аргументы в поддержку этих гипотез. Существуют ли какие-либо проблемы с решением труднее, чем эти две, но они не известны как -hard?Н $\mathsf{NPI}$$\mathsf{NP}$

Изоморфизм групп Изоморфизм графов ≤ m Изоморфизм колец. Также целочисленный факторинг ≤ m кольцевой изоморфизм [ Каял и Саксена ]. Также граф автоморфизм ≤ m граф изоморфизм.$\leq_m$$\leq_m$$\leq_m$$\leq_m$

Мало того, что нет никаких известных сокращений в обратном направлении, но также нет доказательств того, что -редуцирование не происходит из графика Iso в группу Iso [Chattopadhyay, Toran и Wagner ].$\mathsf{AC}^0$

Обратите внимание, что редукция из изоморфизма колец к изоморфизму графа также может привести к редукции от целочисленного факторинга к изоморфизму графа. Для меня такое сокращение было бы удивительным, хотя, возможно, не шокирующим.

(Для автоморфизма графа против изоморфизма графа известно, что их счетные версии эквивалентны друг другу и эквивалентны решению об изоморфизме графов. Однако это не обязательно говорит о многом, поскольку счетная версия двухстороннего сопоставления эквивалентна счетной версии SAT. )

Я не думаю , что есть реальный консенсус относительно того , какие, если таковые имеются, из них на самом деле в . Если любая из этих проблем является N P -завершенной, то P H рушится на второй уровень. Если факторинг N P -полным, то он падает на первый уровень, т.е. N P = гр O N P .$\mathsf{P}$$\mathsf{NP}$$\mathsf{PH}$$\mathsf{NP}$$\mathsf{NP} = \mathsf{coNP}$

Кроме того, я напоминаю, что, используя методы, подобные Ладнеру, можно показать, что любой счетный частичный порядок может быть встроен в порядок для задач в N P (так что это не просто иерархия, а произвольно сложный счетный частичный порядок) ,$\leq_{m}$$\mathsf{NP}$