Polynomial Things

Theorem 8   Cobham Edmonds(Circa 1960): Algorithms that use polynomially bounded resources(time, space) are generally reasonable for moderately sized inputs.

Algorithms that use exponential resources are essentially always not reasonable for moderately sized inputs.

$\mathsf{PRIMERS} = \{x\mid x\textrm{ is a prime number}\}$ is in $\mathbf{coNP}$.
$\mathsf{COMPOSITES} = \{x \mid x \textrm{ is a composite number}\}$ is in $\mathbf{NP}$.
$\mathsf{TAUT} = \{\Phi \mid \textrm{Boolean formula }\Phi\textrm{ is a tautology}\}$¹⁶ is in $\mathbf{coNP}$.
$\mathsf{HAM} = \{G \mid\textrm{ graph }G\textrm{ has a Hamiltonical circuit}\}$ is in $\mathbf{NP}$.¹⁷
$\mathsf{MATCH} = \{G \mid\textrm{ graph } G\textrm{ has a matching}\}$ is in $\mathbf{NP}$.¹⁸
$\mathsf{NONFEAS} = \{F\mid \textrm{linear equations }F\textrm{ have for feasible solution}\}$ is in $\mathbf{NP}$.¹⁹

Definition 8   $NP = \Sigma_1^p$ the class of languages $L$. For which there exists a polynomial time Turing Machine $M$ such that $L = \{x \mid \exists y M(x, y)\}$ and $M$ runs in the polynomial time in $x$. Here $y$ is of polynomial size in regard of $x$.

According to this, $\mathsf{COMPOSITES}$, $\mathsf{HAM}$ and $\mathsf{MATCH}$ are in $\mathbf{NP}$.

Definition 9   $\Pi_q^p = coNP$. The class of languages $L$ for which there exists a Turing Machine $M$ such that $L = \{x\mid \forall y M(x, y)\}$, and $M$ runs in the poly in $x$.

$\mathsf{EXACT CIRCUIT} = \{(G, k) \mid\textrm{ the largest circuit is of length }k\}$ both $\exists$ and $\forall$ are used in the first order logic expression. It is in $\Sigma_2^p$

Definition 10   $\Sigma_i^p$ is the class of languages $L$, for which there exists a Turing Machine $M$ such that $L = \{x\mid \exists y_1\forall y_2\exists y_3\forall y_4\ldots y_i M(x, y_1, y_2, \ldots, y_n)\}$ and M runs in time poly in the size of $x$.

Definition 11   $\Pi_i^p$ is the class of languages $L$, for which there exists a Turing Machine $M$ such that $L = \{x\mid \forall y_1\exists y_2\forall y_3\ldots M(x, y_1, y_2, \ldots, y_n)\}$ and M runs in time poly in the size of $x$.

Definition 12   $\mathbf{P}$ is languages decidable in polynomial time.