Notes - Computational Complexity HT25, Classes
Flashcards
@Define the class $\mathsf P$.
\[\mathsf P = \bigcup_{k \in \mathbb N} \mathsf{DTIME}(n^k)\]
@Define the class $\mathsf E$.
\[E = \mathsf{DTIME}(2^{O(n)})\]
@Define the class $\mathsf{EXP}$.
\[\mathsf{EXP} = \bigcup_{k \in \mathbb N} \mathsf{DTIME}(2^{n^k})\]
@Define the class $\mathsf{NP}$.
\[\mathsf{NP} = \bigcup_{k \in \mathbb N} \mathsf{NTIME}(n^k)\]
@Define the class $\mathsf{NEXP}$.
\[\mathsf{NEXP} = \bigcup_{k \in \mathbb N} \mathsf{NTIME}(2^{n^k})\]
@Define the class $\mathsf{LOGSPACE}$.
\[\mathsf{LOGSPACE} = \mathsf{DSPACE}(\log n)\]
@Define the class $\mathsf{PSPACE}$.
\[\mathsf{PSPACE} = \bigcup_{k \in \mathbb N} \mathsf{DSPACE}(n^k)\]