Если эти задачи являются NP-полными, как существуют алгоритмы полиномиального времени для их решения?

Question

Я изучаю задачи P, NP и NP-Complete, и у меня возникли некоторые вопросы.

Я понимаю, что проблема - это P, если вы можете решить ее за полиномиальное время, а проблема - этоНП, если это проверяется за полиномиальное время.Я также понимаю, что проблема является NP-полной, если она является NP, и ее можно уменьшить из существующей проблемы NP-Complete.

Я знаю, что SAT, 3-SAT, независимый набор, покрытие вершин, гамильтонов цикл,Сумма подмножества и коммивояжёр - все NPC.Но я столкнулся с проблемой, когда мне сказали, что решение, существует ли в графе независимый набор из 5 вершин, на самом деле решается за полиномиальное время вместо NPC.Это тогда смутило меня, потому что я думал, что проблемы с независимыми множествами - это NPC.

Так что это заставило меня задуматься, в каких случаях эти проблемы с NPC не являются NPC и на самом деле P?Когда мне задают проблему, как мне определить, является ли проблема P или NPC?Что, если у проблемы есть решение, решаемое в разное время, я просто не смог придумать его и поэтому пошел по пути NPC.Откуда мне знать, что я допустил ошибку?

Answer 1

решение, существует ли в графе независимый набор из 5 вершин, на самом деле решается за полиномиальное время

Да, решение / поиск независимых наборов фиксированного размера (иликомплиментарно, обнаружение клик фиксированного размера ) имеет алгоритм грубой силы полиномиального времени, обычно что-то вроде n ^k с k будучи фиксированным размером - в вашем случае n ⁵ .

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

Answer 2

Существует аналогия, которая может помочь вам подумать об этом, хотя это не одно и то же.Существует математическое доказательство того, что вы не можете отсортировать массив произвольной длины менее чем за O (n * log (n)).Однако, если вход «маленький» или если вы знаете что-то о входе, например, что он содержит только k символов, то вы можете использовать другие методы, чтобы решить его быстрее, используя O (n) алгоритмы (например, Redixsort).

Когда мы пытаемся обобщить проблему, так как у нас нет никаких предварительных знаний о входных данных, все становится сложнее (а иногда и NP-Complete сложнее).

Answer 3

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

При заданном числе k и графе n вершин, проблемапоиск независимого набора k вершин - это отдельная задача , для которой существует решение за полиномиальное время.Это не проблема оптимизации.

Решение ограничено тем фактом, что существует не более C(n, k) подмножеств из пяти вершин, и для каждого подмножества необходимо проверить не более C(k, 2) ребер.Каждый из них является полиномиальным от n для константы k.