Согласование алгоритма Куайна-МакКласки

Question

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

"он также дает детерминированный способ проверить,достигнута минимальная форма булевой функции "

, а

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

Мысли?

ps Есть ли плагин Visual Studio, который может уменьшить условную логику, применяя этот алгоритм к выделенному коду?

Answer 1

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

Расхождение, вероятно, связано с тем, что вы не до конца понимаете определение NP-hard: http://en.wikipedia.org/wiki/NP-hard

Answer 2

В этих утверждениях нет ничего противоречивого.
Вы можете быть смущены тем, что означает "детерминистический" в этом контексте:

В компьютерной науке детерминированный алгоритм - это алгоритм, который в неформальнойсроки, ведет себя предсказуемо.При конкретном вводе он всегда будет выдавать один и тот же вывод, а базовый компьютер всегда будет проходить через одну и ту же последовательность состояний.

From wikipedia

В этом смысле почти все широко используемые CS-алгоритмы являются детерминированными.

Я уверен, что вы уже знаете, что означает «NP-hard»:)