Вопросы с тегом «separation»

Явное разделение между конструктивностью во времени и конструктивностью в пространстве?

Покажите функцию которая конструируется в пространстве, но не является временной.е( н )е(N)f(n) Связана ли эта проблема с возможным разделением между классами сложности DTIME (f (n)) и SPACE (f...

Можно ли использовать описательную версию сложности теоремы Райса для разделения AC0 и PSPACE?

В этом вопросе было отмечено, что существуют версии описательной сложности теоремы Райса. Я нашел доказательство следующей теоремы: Учитывая класс сложности C , нетривиальные свойства языков в C не могут быть вычислены в C Ранее я опубликовал найденное мной доказательство, но поскольку оно было...