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

Ссылки сюда (2) →

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

• DLOGSPACE ≠ P
• PSPACE ≠ P

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.