|
noun phrase 名詞句 =========================== 「 NP 」を含む部分一致用語の検索リンク〔 1 件 〕 ・NP ： noun phrase 名詞句
NPとは、計算量理論における問題の集まりで、Non-deterministic Polynomial time（非決定性多項式時間）の略である。 == 定義 == NP の定義は次の2つである、ただしこれらはお互い同値であることが証明されている。 # 非決定性チューリングマシンによって多項式時間で解くことができる問題。 # yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題。 端的に説明するときは 2番目の定義（多項式時間で検算可能）が用いられることが多い。 なお NP はクラス P 同様、判定問題のクラスであり yes/no で答えることの出来ない問題は NP には属さない。 誤解されることが多いが、NP は多項式時間で解けない問題のクラスではない（Not P の略ではない)。上記の定義は全てのクラス P の問題にも当てはまるので、クラス P は クラス NP に含まれる。 NPはPよりも大きいと予想されているが、証明されていない。P≠NP予想という。 NPに属する任意の問題と少なくとも同じくらい難しい問題をNP困難であるといい、そのうちNPに属するものをNP完全問題という。これらの概念は正確には多項式時間帰着を使って定義する。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「NP」の詳細全文を読む スポンサード リンク
|