Изменения

# Определим $polyL$ как $\cup_{c>0}DSPACE(\log^c n)$. $PATH = \{\langle G, s, t\rangle,$ в ориентированном графе $G$ есть путь из $s$ в $t\}$. Докажите, что $PATH \in polyL$.

# Обозначим как $DP$ множество языков $L$, для которых найдутся $L_1 \in NP$ и $L_2 \in coNP$, такие что $L = L_1 \cap L_2$. Рассмотрим язык $EXACTINDSET = \{\langle G, k\rangle | \text{ максимальное}$ $\text{независимое множество в графе $G$ имеет размер $k$}\}$. Докажите, что $EXACTINDSET$ является полным для класса $DP$ относительно полиномиального сведения.

# Предложите разрешимый язык из $P/poly$, который не лежит в $P$.

# Докажите, что $Sparse \subset P/poly$ ($Sparse$ - множество языков, которые имеют лишь полиномиальное число слов каждой длины).

# Докажите, что существует язык из $DSPACE(2^{O(n)})$, которой не принадлежит $SIZE(2^{o(n)})$.

# Докажите, что если $EXP \subset P/poly$, то $EXP = \Sigma_2$.