minicomplexity
2N
 All problems that can be solved by 2NFAs of size polynomial in $h$.
 The class of families of problems $\mathcal L=(L_h)_{h\geq1}$ for which there exists a family of 2NFAs $\mathcal M=(M_h)_{h\geq1}$ and a polynomial $p$ such that every $M_h$ has at most $p(h)$ states and solves $L_h$.
 Introduced by Sakoda Sipser 1978, as the analog of  NP  for 2FAs (in place of Turing machines) and for size (in place of time).
 – no record –
 – no record –
1N 2N/uny
1N 2N/uny 1D re-1D re-1N co-1D rc-1D 1D/uny 1N/uny RD/uny RN/uny SD/uny SN/uny 2D/uny re-1D/uny re-1N/uny re-RD/uny re-RN/uny re-SD/uny re-SN/uny re-2D/uny re-2N/uny co-1D/uny rc-1D/uny
 re-2N
 – no record –
SN 2D
SN 2D RD RN SD re-RD re-RN re-SD re-SN re-2D
 – no record –
 – no record –