EXP - 国立公園

EXP

定義

$ \mathbf{EXP} := \bigcup_{p : \text{ polynomial}} \mathbf{DTIME}(2^{p(n)}) = \bigcup_k \mathbf{DTIME}(2^{n^k})

性質

$ \textbf{EXP} \ne \textbf{NEXP} \Rightarrow \textbf{P} \ne \textbf{NP}