Временная и пространственная сложность алгоритмов/Задачи/dlogspace-pspace-gap

Материал из DISCOPAL
Перейти к: навигация, поиск

Покажите, что должно выполняться хотя бы одно из неравенств (несовпадений) классов сложности:

  • Заметим, что если у вас вряд ли получится доказать эти неравенства по отдельности.