NP
定義
$ \textbf{NP} := \bigcup_{c > 0} \textbf{NTIME}(n^c)
または
言語$ L \subseteq 2^*について, $ Lが$ \textbf{NP}であるとは, 多項式関数$ p : \mathbb{N} \to \mathbb{N}と多項式計算時間のTM$ M(varifier)が存在して $ x \in L \iff \exists u \in 2^{p(|x|)}. [M(\langle x, u \rangle) = 1]
を満たすことである
性質
関係