Основное правило, чтобы узнать, может ли проблема быть NP-полной

Этот вопрос был вдохновлен комментарием к StackOverflow .

Помимо знания NP-полных проблем книги Гэри Джонсона и многих других; Есть ли эмпирическое правило, чтобы узнать, выглядит ли проблема как NP-полная?

Я не ищу что-то строгое, но что-то, что работает в большинстве случаев.

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

complexity-theory np-complete intuition Виталий Олегович
источник

Мое эмпирическое правило простое: если это не пахнет проблемой, с которой я уже знаком, это, вероятно, NP-сложный (или хуже).

Джефф

@JeffE, конечно, вы уже знакомы с довольно многими проблемами ... новички в CS могут быть не в состоянии использовать то же правило.

Джо

@Joe: правда. Возможно, было бы лучше сказать: если вы не поняли проблему из учебника, это, вероятно, NP-трудный.

Джефф

Другой способ выразить это: удивительно, когда проблема не NP-сложна, а не когда проблема NP-сложна.

Джо

Ответы:

Это мой личный подход к определению, является ли проблема (т. Е. Язык ) NP-полной или нет. Если оба эти условия проверены: $L$

Я чувствую, что тестирование, если экземпляр находится в подразумевает, что мне нужно проверить все комбинации некоторого вида $I$ $L$
и что нет никакого способа разделить такую комбинацию на две более мелкие

$L$

$S$ $S$ $S_1$ $S_2$ $S_1$ $S_2$

$A$ $C$ $B$ $A$ $B$ $B$ $C$

Откровенно говоря, этот подход очень прост: я пытаюсь найти (полиномиальный) алгоритм для данной задачи. Если я не могу его найти, то проблема становится «сложной» с моей точки зрения. Затем идут все рассуждения о NP-полноте: смогу ли я зашифровать существующую NP-полную проблему в эту? (И поскольку это обычно намного сложнее, я пытаюсь еще раз найти алгоритм полинома ..)

Я подозреваю, что это обычный способ мышления. Однако это остается довольно трудно применить для неизвестных проблем. Я лично помню, как меня удивил один из первых примеров NP-полноты, который мне сказали: проблема клики . Это было так просто проверить! Поэтому я полагаю, что этот опыт во многом связан с этим. Также интуиция иногда бывает бесполезной. Я помню, как мне несколько раз говорили о двух почти одинаковых проблемах, но одна была в P, а другая с небольшим изменением была NP-полной.

Мне еще не удалось найти хороший пример (мне нужна помощь здесь), но это похоже на проблему почтовой корреспонденции : это неразрешимая проблема, но некоторые варианты разрешимы.

jmad
источник

+ 1

$+1$

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

hugomg

Примером является проблема Longest Common Subsequence, которая находится в P для 2 последовательностей, но попадает в NP-Hard с большим количеством.

Кристиан Вьельма

Еще один взгляд на сложность проблемы связан с сообществом игр и головоломок, где практическое правило гласит, что «проблемы настолько сложны, насколько это возможно» (а исключения происходят из скрытых структур в проблеме - пример Массимо, определяющего в комментарии - хороший пример этого); хитрость в том, чтобы понять, насколько сложной может быть проблема:

$n$
Головоломки, включающие в себя последовательность перемещений в ограниченном пространстве состояний, находятся в PSPACE (поскольку «дерево перемещений» обычно можно исследовать стандартным способом глубины, требующим только хранения для полиномиального числа конфигураций), и они, как правило, полны PSPACE; классическим примером этого является час пик.
Игры с полиномиально ограниченной глубиной также находятся в PSPACE; при этом используется характеристика PSPACE в качестве APTIME, поскольку обычная минимально-максимальная характеристика стратегий идеально имитирует чередующуюся машину Тьюринга с ее характеристикой, поскольку «существует ход для игрока A, такой что на каждый ответный ход от игрока B существует ответ ход за игроком А, таким, что ... 'и т. д. Они также имеют тенденцию быть PSPACE-завершенными; Hex и обобщенные игры Tic-Tac-Toe являются примерами этого.
Игры без ограничения по глубине дерева, но игра в (полиномиально) ограниченном пространстве, находятся в EXPTIME, так как общее количество позиций экспоненциально, а весь график может быть построен и исследован за полиномиальное время по количеству позиций (и, таким образом, по экспоненте в целом) ; Эти игры, как правило, полны опыта. Шахматы, шашки и го все попадают в эту категорию.

Стивен Стадницки
источник