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

16

Предположим , что пNп . Nпя - класс задач в Nп которых нет ни в п ни в Nп -твердых. Вы можете найти список проблем предположительно Nпя здесь .

Теорема Ладнера говорит нам, что если то существует бесконечная иерархия задач , то есть существуют проблемы которые сложнее, чем другие проблемы.Н П И Н П И Н П ИNппNпяNпяNпя

Я ищу кандидатов на такие задачи, т.е. меня интересуют пары задач
- , - и предполагаются как , - известно , что сводится к , - но нет никаких известных сокращений от к . A B N P I A B B AA,ВNп
AВNпя
AВ
ВA

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

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

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

Мухаммед Аль-Туркистани
источник
3
Размещено здесь на основании предложения Каве после истечения срока действия вознаграждения CS Stackexchange без удовлетворительного ответа.
Мухаммед Аль-Туркистани

Ответы:

18

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

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

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

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

Я не думаю , что есть реальный консенсус относительно того , какие, если таковые имеются, из них на самом деле в . Если любая из этих проблем является N P -завершенной, то P H рушится на второй уровень. Если факторинг N P -полным, то он падает на первый уровень, т.е. N P = гр O N P .пNппЧАСNпNпзнак равносоNп

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

Джошуа Грохов
источник
1
Я нахожу тихое смешение подсчета версий и версий решений довольно запутанным. Кольцо является конечной структурой, а (вариант решения) изоморфизма конечных структур является GI-полным. Таким образом, вариант решения кольцевого изоморфизма не сложнее, чем GI, и не сложнее, чем целочисленный факторинг.
Томас Климпел
1
@ThomasKlimpel: просто b / c изо конечных структур является GI-полным, это не значит, что для любого конкретного класса конечных структур проблема изо является GI-полной. А именно группа iso не известна и не считается GI-полной. Кольцо iso, когда оно дается таблицами сложения / множеством, также вряд ли будет GI-полным, учитывая, что оно находится в . Версия RingIso, на которую я ссылаюсь в ответе выше, является той, что дана родом и отношениями. TIME(O(nlogn))
Джошуа Грохов
@ThomasKlimpel: если при «тихом микшировании» вы ссылаетесь на заключенный в скобки абзац, то упомянутые здесь эквивалентности выражаются в терминах сокращений Тьюринга за полиномиальное время (сокращений Кука), а не сокращений «многие-один».
Джошуа Грохов
Хорошо, я прочитал начало ссылки сейчас. Кольцо задается таблицами сложения / мульт, но они имеют каноническое сжатое представление для колец (поскольку аддитивная группа абелева), поэтому результат полноты GI для конечных структур не имеет значения. Я бы не охарактеризовал это представление как «род и связь», потому что это звучит как «тихое смешение», на которое я изначально жаловался. Несвязанное замечание: я не ссылался на заключенный в скобки абзац и не предполагал, что кольцевой изоморфизм должен быть GI-полным, просто он не должен быть сложнее, чем GI.
Томас Климпел
@ThomasKlimpel: Извините, вы правы, это не совсем отношения и отношения. (И я неправильно понял ваше замечание о GI-complete против «не сложнее, чем GI».) Мне показалось, что я понял, что вы имели в виду под «тихим микшированием», но, учитывая ваш последний комментарий, я больше не понимаю. Но, возможно, это не так уместно для cstheory.stackexchange, и вы можете написать мне напрямую, чтобы уточнить мое понимание (после чего я мог бы обновить ответ, если это необходимо).
Джошуа Грохов