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

Версия 00:36, 4 марта 2021

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

• DLOGSPACE ≠ P
• PSPACE ≠ P.

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