Как проблема может быть в NP, быть NP-сложной, а не NP-полной?

14

Долгое время я думал, что задача была NP-полной, если она (1) NP-сложная и (2) в NP.

Однако в известной статье «Метод эллипсоидов и его последствия в комбинаторной оптимизации» авторы утверждают, что проблема дробного хроматического числа принадлежит NP и является NP-сложной, но пока неизвестно, что она NP-полная. На третьей странице статьи авторы пишут:

... отметим, что задача упаковки вершин графа в некотором смысле эквивалентна проблеме дробных хроматических чисел, и прокомментируем явление, что эта последняя проблема является примером задачи в которая является N P- трудной но (на данный момент) не известен как N P -полный.NPNPNP

Как это возможно? Я упускаю тонкую деталь в определении NP-полной?

Остин Бьюкенен
источник

Ответы:

27

Кажется, проблема заключается в том, какие сокращения используются для каждого из них, и они используют разные: они, вероятно, означают « -hard wwt уменьшений Cook» и « N P -complete wrt уменьшений Karp».NPNP

Иногда люди используют версию -hardness сокращения Кука, потому что она применима к более общим вычислительным задачам (а не только к решению проблем). Хотя в первоначальном определении как N P -hardness, так и N P -completen использовались сокращения Кука (сокращения Тьюринга за полиномиальное время), стало редкостью использовать сокращения Кука для N P -полноты (если это не указано явно). Я не помню ни одной недавней статьи, в которой использовалось N P -complete для обозначения N P -complete относительно сокращений Кука. (В качестве стороны отметим первую проблему, которая должна быть доказана до Н ПNPNPNPNPNPNPNP-Твердо было TAUT, а не SAT, и полнота для SAT подразумевается в этом доказательстве.)

Теперь, если вы посмотрите на раздел 7 статьи, внизу страницы 195, вы увидите, что они означают -твердость по сравнению со снижением по Тьюрингу.NP

Таким образом, они имеют в виду, что проблема заключается в , это трудно для N P по сравнению с уменьшением Кука, но неизвестно, что это трудно для N P по сравнению с уменьшением Карпа (многочленное сокращение за многократное время).NPNPNP

Кава
источник
1
Вы имеете в виду DNF-тавтологию под Taut? Это не CoNP-полный? Потому что CNF-тавтология тривиальна.
Tayfun Pay
1
@TayfunPay: Скорее всего тавтология для произвольных формул, а не только CNF или DNF. И Co-NP-complete и NP-complete - это то же самое, что и Cook-сокращения, поэтому Каве упоминает этот анекдот.
frafl
1
@Tayfun, Кук доказывает это для общих формул и использует это DNF-TAUT является следствием в статье. Оба NP- трудны в отношении Кука.
Kaveh
@frafl, «NP-полная» определена в статье Карпа 1972 года . Документ Кука 1971 года определяет сокращения Кука и доказывает, что TAUT является NP-сложным по отношению к ним. Это также доказывает, что ряд проблем эквивалентен сокращению Кука. Однако NP-полнота явно не указана в оригинальной статье.
Kaveh