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)\]



Related posts