Мы знаем, что . Из теоремы Савича и из теоремы пространственной иерархии . Итак, поскольку мы не знаем, , мы не знаем, , или мы знаем, что ? Кто-нибудь пытался доказать, что \ mathcal L ^ 2 \ subseteq \ mathcal P ? Каковы последние результаты или усилия в этом направлении? Я пытался написать опрос на эту тему, но не нашел ничего актуального.
Кроме того, существует или нет проблема которая не является -полной, является открытым вопросом, и такое существование подразумевает , так как каждый задачи является полным для . Но разве мы не знаем, что ? Кто-нибудь пытался доказать это? Опять же, каковы последние результаты или усилия на этом пути?
Может быть, я что-то упустил или искал неправильно, но я не смог найти никого, кто работал над вопросами и .
источник
Ответы:
Вы можете проверить следующую бумагу:
Трансляционные леммы, полиномиальное время и -пространство(logn)j Рональда В. Книга (1976).
Рисунки 1 и 2 в статье дают краткое изложение того, что известно, а что неизвестно.
Я положил теорему 3.10 в статье здесь:
источник