3622
правки
Изменения
→4. Сложность по памяти, классы PS, L, NL, coNL
## Оформить правильно
=== 4. Сложность по памяти, классы PS, L, NL, coNL , EXP, NEXP ===#[[Класс PS. Связь класса PS с другими классами теории сложности]] (0.51)
## Отформатировать по правилам
## Как-то помёрджить с [[Класс PS]]
#[[Теорема Сэвича. Совпадение классов NPS и PS]] (1)
## Отформатировать по правилам
#[[PS-полнота языка верных булевых формул с кванторами (TQBF)]] (1)
## Отформатировать по правилам
# [[PS-полнота задачи Generalized geography]] (4)
## Отформатировать по правилам
## Привести примеры, где может быть актуально решать такую задачу
#[[Классы L, NL, coNL]] (3)
## Отформатировать по правилам
## Добавить больше неформальных пояснений к классам
## Добавить ещё несколько утверждений про связи классов L с другими
## Помёрджить с этим конспектом и другими из треша: [[NL-полнота]]
#[[Полнота относительно L-сведения. NL-полнота. P-полнота]] (2)
## Отформатировать по правилам
#[[Теорема Иммермана]] (2)
## Отформатировать по правилам
# [[Классы EXP и NEXP]] (4)
## Смёрджить два конспекта и отформатировать по правилам: [[Классы EXP, NEXP. Полнота языков EXP и NEXP]], [[Теорема о связи вопросов EXP=NEXP и P=NP]]
=== 5. Полиномиальная иерархия ===
