Почему проблемы NPI не все одинаковой сложности?

11

Как можно взглянуть на проблему и причину, по которой это скорее NP-Intermediate, чем NP-Complete? Часто довольно просто взглянуть на проблему и сказать, является ли она NP-Complete или нет, но мне кажется, что гораздо сложнее определить, является ли проблема NP-Intermediate, так как грань между ними кажется довольно тонкой. классы. По сути, я спрашиваю, почему проблема, которая может быть проверена за полиномиальное время (если она вообще существует), но не решена за полиномиальное время (если P dos не равна NP), не будет сводиться за полиномиальное время друг к другу. Кроме того, есть ли способ показать, что проблема NP-Intermediate аналогична тому, как показано, что проблема NP-Hard, например редукция или какой-либо другой метод? Будем благодарны за любые ссылки или учебники, которые помогут мне понять класс NP-Intermediate.

Джесси Стерн
источник
2
«проблема, которую можно решить за полиномиальное время», я полагаю, вы имеете в виду «проблему, которую можно проверить за полиномиальное время».
Каве
2
Существует класс GI-полных задач, полиномиально эквивалентных изоморфизму графа. GI - главная проблема, предположительно являющаяся NP-промежуточной
Мухаммед Аль-Туркистани
1
Кстати, название вводит в заблуждение, равенство двух проблем сложности относительно сокращения (например, сокращения Карпа) уже определено, я бы предложил вам изменить его на что-то вроде «Почему проблемы NPI не все одинаковой сложности?».
Каве
@kaveh Сделал все правки. Спасибо за еще один отличный ответ!
Джесси Стерн
1
«Часто довольно просто посмотреть на проблему и сказать, является ли она NP-Complete или нет». ИМХО, это не могло быть дальше от истины!
Махди Черагчи

Ответы:

20

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

Есть искусственные проблемы , которые могут быть доказаны , чтобы быть в с использованием обобщения теоремы Ландера (также см это ) при условии , что N PP .NPINPP

Также проложенный версия проблем являются Н Р ЯNEXP-completeNPI предполагая , (смотри также это и это ).NEXPEXP

Проблемой в часто считается N P I, когда:NPNPI

  1. при разумных допущениях мы можем показать, что это не но неизвестно, что он находится в P ,NPCP

  2. при разумных допущениях мы можем показать, что его нет в но неизвестно, что он находится в N P C ,PNPC

и когда - то только тогда , когда мы не можем показать , что в или P .NPCP

Примером разумного предположения является экспоненциальная гипотеза времени (или некоторые другие предположения о вычислительной жесткости ).

По сути, я спрашиваю, почему проблема, которая может быть решена за полиномиальное время (если она вообще существует), но не решена за полиномиальное время (если P не равен NP), не будет сводиться за полиномиальное время друг к другу.

NPCPП Н ПPPNP

Кава
источник
2
«2. мы можем показать, исходя из разумных предположений, что его нет в P, но неизвестно, что он находится в NP.
Тайсон Уильямс
@Victor, нет, неизвестно, что не равен , и они отличаются, если и различны. Откат вашего редактирования. Н П С П Н ПPNPCPNP
Каве
@ Каве, я думаю, он думал о тривиальных языках ( and ), но вы исключаете их из P.{ 0 , 1 } {0,1}
от
@ Диего, ну, для них ничего не сводится, но ты прав. Я починю это.
Каве
@ Каве и Диего: Да, я думал об этих тривиальных языках.
Виктор Стафуса
12

Типичный случай, когда проблема в также лежит в или . Предполагая, что полиномиальная иерархия не разрушается, такая проблема не может быть -полной. Примеры включают целочисленную факторизацию, дискретный логарифм, изоморфизм графов, некоторые задачи решетки и т. Д.с о Н П с о А М Н ПNPcoNPcoAMNP

Махди Черагчи
источник
9

Другой типичный случай проблемы - когда есть свидетель длины но меньше, чем . Проблема существования клики размером в графе является типичным примером - в этом случае свидетель (конкретная клика) требует битов.ω ( log n ) n O ( 1 ) log n O ( log 2 n )NPIω(logn)nO(1)lognO(log2n)

Принимая гипотезу об экспоненциальном времени, такая проблема проще, чем полная задача (которая требует времени )), но сложнее, чем проблема полиномиального времени.exp ( n O ( 1 ) )NPexp(nO(1))

Дэвид Харрис
источник