algorithm - これはNPの問題ですか？

Question

最近、 NPとPに関する記事を読みました。与えられた単語の組み合わせを見つける問題は NP 問題ですか? たとえば、指定された単語antoの場合、結果は anot、toan などになります。私が知ったように、多項式時間で問題の解を確認できるときはいつでも、それは NP の下にあることを意味します。組み合わせの問題は NP に入るのですか？

これは、私が NP と P をよく理解しているかどうかを知るためのものです。

Answer 1

この問題は NP にはありません。なぜなら、NP は決定問題、つまり「はい」か「いいえ」で答えられる問題で構成されているからです。しかし、この問題は、「文字の集合、辞書、およびその辞書にあるいくつかの単語が与えられた場合、辞書にはあるが辞書にはない文字のアナグラムがあるか」と言い換えることで、簡単に決定問題にすることができます。今までの単語リストは？」

この問題は多項式時間 (したがって、非決定論的多項式時間) で確実に解決できます。これは、辞書と入力単語のサイズの多項式に時間がかかる可能性のある各単語をチェックする辞書全体を反復処理できるためです。ただし、はい/いいえの質問をしていないため、それは P または NP のいずれにも当てはまりません。

お役に立てれば！

Answer 2

AFAIK 問題の解決策がないため、NP が決定問題であることはわかっています。残っているのは、多くの場合、貪欲なアルゴリズムまたは遺伝的アルゴリズムであり、多項式時間で適切な解を見つけることができます。ブルートフォースは非現実的であり、最適な解決策を見つけるかどうかさえわかりません。