Есть ли проблемы «NP-Intermediate-Complete»?

13

Предположим, что P NP.

Теорема Ладнера гласит, что существуют промежуточные проблемы NP (проблемы в NP, которые не находятся ни в P, ни в NP-Complete). Я нашел несколько завуалированных ссылок в Интернете, которые предполагают (я думаю), что в NPI существует много «уровней» взаимно сводимых языков, которые определенно не все сводятся в один.

У меня есть несколько вопросов о структуре этих уровней.

  1. Существуют ли проблемы «NP-Intermediate-Complete» - то есть, проблемы NP-Intermediate, к которым любая другая проблема NP-Intermediate сводится по времени?
  2. Сортируйте NP - P по классам эквивалентности, где взаимная сводимость - это отношение эквивалентности. Теперь наложите порядок на эти классы эквивалентности: если задачи в B сводятся к задачам в A (поэтому ясно, что класс эквивалентности NP-Complete является максимальным элементом). Является ли это полным порядком (т.е. проблемы расположены в бесконечной нисходящей цепочке)? Если нет, имеет ли «древовидная структура» частичного упорядочения конечный фактор ветвления?A>BBA
  3. Есть ли другие интересные известные структурные компоненты NP - P? Есть какие-нибудь интересные открытые вопросы о базовой структуре?

Если что-то из этого в настоящее время неизвестно, мне было бы интересно это услышать.

Благодарность!

GMB
источник
3
Слабая версия этого заключается в том, что существуют проблемы «граф-изоморфизм-полный».
Суреш Венкат
7
ππNPNPP=NP
Спасибо, Бруно, можно ли найти эту информацию в оригинальной статье Ладнера или есть другие источники?
GMB
Вы также можете взглянуть на статью Дауни и Фортнау: « Равномерно жесткие языки» ; в котором доказательство теоремы Ладнера, приведенное в Приложении A.1, показывает, что полиномиальные степени времени вычислимых языков имеют плотное частичное упорядочение. Они также предполагают, что если в NP существуют равномерно жесткие множества, то существуют неполные равномерно жесткие множества.
Марцио Де Биаси
1
для другой ссылки на 1. и, возможно, полезного ресурса, см . ответ Райана и цитируемую в нем статью Шоенинга.
Сашо Николов

Ответы:

31

На самом деле у меня нет ссылок на эти результаты - их нетрудно доказать, если вы понимаете теорему Ладнера.

  1. Нет, для любого NP-неполного множества A существует другое множество B строго между A и SAT.

  2. Эти классы эквивалентности известны как степени многочлена-много-один. Вы можете встроить любой конечный набор в градусы ниже NP. В частности, степени не являются полностью упорядоченными или конечно разветвленными.

  3. Все зависит от того, что вы подразумеваете под «интересным». Существует огромная теория структуры степеней вычислимых множеств (см. , Например , книгу Соаре), и многие из этих вопросов не были перенесены на множества полиномиального времени. Например, можете ли вы иметь наборы NP A и B, чье соединение эквивалентно SAT, а чье соответствие эквивалентно пустому набору?

Лэнс Фортноу
источник
1
ABC(x,y)CxAyB
8
Это термины теории решеток : объединение подмножества является его наименьшей верхней границей (если она существует) и соответствует наибольшей нижней границе.
Бруно