Естественные кандидаты на иерархию внутри 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 \in \mathsf{NP}$
$A$ $B$ $\mathsf{NPI}$
$A$ $B$
$B$ $A$

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

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

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

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

Итак, вы ищете такие задачи

, что

где

P \in N P

$P \in \mathrm{NP}$

P_{1} \leq_{p} P \leq_{p} P_{2}

$P_1 \leq_p P \leq_p P_2$

P_{1} \in N P I

$P_1 \in \mathrm{NPI}$

P_{2} \in N P C

$P_2 \in \mathrm{NPC}$

Рафаэль

Да, но нет известного снижения с P до P1 (аналогично, никакого известного снижения с P2 до P).

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

Есть несколько проблем со статусом, похожим на факторинг, см. эту статью от Papadimitriou theory.stanford.edu/~megiddo/pdf/papadimX.pdf

Маркос Вильягра

кроме того, у нас есть очень хороший список в cstheory cstheory.stackexchange.com/questions/79/…

Маркос Вильягра

почему список, на который ссылается Маркос, не является ответом на ваш вопрос?

Суреш

Ответы:

Я нашел хорошую проблему под названием ModularFactorial . Возьмите в качестве входных данных два -значных целых числа и и выведите $n$ $x$ $y$ . Эта проблема,крайней мере столь же труднокакфакторинги не знаюбудет трудно дляФНП. Ссылка - недавняя (и красивая) книга Кристофера Мура и Стефана Мертенса«Природа вычислений», стр. 79. $x! \mod y$

Маркос Вильягра
источник

Я считаю, что ОП ищет проблемы в НП. Можете ли вы переформулировать это как решение проблемы?

Зак Лэнгли

FNP - это версия функции (т. Е. Проблемы поиска) NP. Фактически, факторинг не в NP, а в FNP. Например, проблема решения для факторинга тривиальна, сложность просто O (1), но проблема поиска - сложная часть. Так как ОП привел факторинг в качестве примера, я думаю, что это также правильный ответ.

Маркос Вильягра

Факторинг можно переформулировать в решение проблемы следующим образом: если задано целое число

и целое число

, содержит ли

фактор

? Существует ли аналогичная версия решения проблемы ModularFactorial?

n

$n$

k

$k$

n

$n$

d

$d$

1 < d \leq k

$1 < d \le k$

Зак Лэнгли

@ Маркос, спасибо. Меня интересует решение проблем в НП.

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

@ZachLangley, да, конечно, я согласен, но я думал о другой версии решения, а именно: "есть ли у x фактор?" Ответ здесь просто "да" всегда. Вы можете сделать то же самое с модульным факториалом, дать целое число k и решить, если

больше чем

или нет.

x! \mod y

$x!\mod y$

k

$k$

Маркос Вильягра