.np .np%E3%81%AE%E6%A6%82%E8%A6%81

ウィキペディア

.np

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/10/24 07:48 UTC 版)

.npはネパールに割り当てられている国別コードトップレベルドメイン(ccTLD)である。管理はMercantile Communicationsにより行われている。

NP

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/01/21 20:47 UTC 版)

この項目では、計算量について説明しています。その他の用法については「NP (曖昧さ回避)」をご覧ください。

計算複雑性理論における NP (英: Non-deterministic Polynomial time)は、複雑性クラスのひとつであり、答えがyesとなるような問いに対して、多項式時間で検証できる証拠が存在する決定問題のクラスである。

定義

NP は、NTIMEを使って次のように定義される^[1]。

${\displaystyle {\textsf {NP}}=\bigcup _{k\in \mathbb {N} }{\textsf {NTIME}}(n^{k})}$

多項式階層の包含関係図

Pは、決定性チューリングマシンを使って多項式時間で解ける問題のクラスである。定義より明らかに ${\displaystyle {\textsf {P}}\subseteq {\textsf {NP}}}$ 一覧・ カテゴリ