Иерархии в NP (при условии, что P! = NP)

30

Предполагая, что P! = NP, я полагаю, что было показано, что есть проблемы, которых нет в P и не NP-Complete. Предполагается, что изоморфизм графов является такой проблемой.

Есть ли доказательства наличия таких «слоев» в NP? т.е. иерархия из более чем трех классов, начинающихся с P и заканчивающихся в NP, так что каждый является надлежащим супернабором другого?

Возможно ли, что иерархия бесконечна?

Арьябхата
источник
1
Иерархии не иерархии!
txwikinger
@txwikinger. Исправлено :-)
Арьябхата
связанные: 1
Каве

Ответы:

30

Да! Фактически, между P и NP-полными существует бесконечно сложная иерархия все более сложных задач в предположении, что P! = NP. Это прямое следствие доказательства теоремы Ладнера (которая установила не пустоту NP \ P)

Формально мы знаем, что для любого множества S, не входящего в P, существует S 'не в P, такое, что S' сводимо по Карпу к S, но S не сводимо по Куку к S '. Следовательно, если P! = NP, то существует бесконечная последовательность множеств S 1 , S 2 ... в NP \ P такая, что S i + 1 сводится по Карпу к S i, но S i не сводится по Каку к S i + 1 .

Следует признать, что подавляющее большинство таких проблем носит крайне неестественный характер.

Даниэль Апон
источник
11
Фактически, теорема Ладнера показывает, что для любых двух множеств S и T, если S Karp-сводится к T, но T не Karp-сводится к S, то существует множество S 'такое, что S' правильно лежит между S и T ( в частичном порядке при сокращениях Карпа).
Джошуа Грохов
11

Существует понятие «ограниченного недетерминизма», которое ограничивает недетерминированные биты, необходимые машине Тьюринга для достижения решения. Класс NP требует, например, O (n) битов. Ограничение недетерминированных битов полилогом определяет бесконечную иерархию классов сложности, называемую \ beta P иерархией, все с полными собственными проблемами.

См., Например, следующую статью для подробностей: Голдсмит, Леви, Мундхенк, «Ограниченный недетерминизм», SIGACT News, том 27 (2), страницы 20-29, 1996.

Имран Рауф
источник