Это проблема NP?
Я недавно прочитал статьи о NP и P. Таким образом, проблема поиска комбинаций данного слова является проблемой NP? Например, данное слово anto, результат может быть anot, toan и так далее. Как я узнал, всякий раз, когда мы можем проверить решение проблемы за полиномиальное время, это означает, что оно относится к NP. Таким образом, проблема комбинации входит в NP?
Это просто для того, чтобы понять, хорошо ли я понял NP и P.
2 ответа
Эта проблема не в NP, потому что NP состоит из проблем решения, проблем, которые имеют ответ да или нет. Однако эту проблему можно легко превратить в проблему решения, перефразировав ее как "учитывая набор букв, словарь и некоторое количество слов из этого словаря, есть ли анаграмма этих букв, которая есть в словаре, но не в список слов у нас так далеко?
Эта проблема определенно решаема за полиномиальное время (и, следовательно, недетерминированное полиномиальное время), потому что вы можете просто выполнять итерацию по словарю, проверяя каждое возможное слово, что занимает полиномиальное время по размеру словаря и входного слова. Однако это не делается ни в P, ни в NP, поскольку вы не задаете вопрос "да / нет".
Надеюсь это поможет!
AFAIK Я знаю, что NP - это проблема решения, потому что нет решения проблемы. Часто остается жадный алгоритм или генетический алгоритм, который может найти хорошее решение за полиноминальное время. Грубая сила нецелесообразна, и она даже не уверена, найдет ли она оптимальное решение.