Это проблема NP?

Question

Я недавно читал статьи о NP и P . Таким образом, проблема поиска комбинаций данного слова является проблемой NP? Например, если задано слово anto , результатом может быть anot, toan и так далее. Как я узнал, всякий раз, когда мы можем проверить решение проблемы за полиномиальное время, это означает, что оно относится к NP. Таким образом, проблема комбинации входит в NP?

Это просто для того, чтобы понять, хорошо ли я понял NP и P.

Answer 1

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

Эта проблема определенно решаема за полиномиальное время (и, следовательно, недетерминированное полиномиальное время), потому что вы можете просто выполнять итерацию по словарю, проверяя каждое возможное слово, которое занимает многочлен времени вразмер словаря и входного слова.Однако это не происходит ни в P, ни в NP, поскольку вы не задаете вопрос «да / нет».

Надеюсь, это поможет!

Answer 2

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