На , , , и

9

Мы знаем, что . Из теоремы Савича и из теоремы пространственной иерархии . Итак, поскольку мы не знаем, , мы не знаем, , или мы знаем, что ? Кто-нибудь пытался доказать, что \ mathcal L ^ 2 \ subseteq \ mathcal P ? Каковы последние результаты или усилия в этом направлении? Я пытался написать опрос на эту тему, но не нашел ничего актуального.LNLPNPNLL2LL2LPL2PL2PL2P

Кроме того, существует или нет проблема NP которая не является NP -полной, является открытым вопросом, и такое существование подразумевает LNP , так как каждый L задачи является полным для L . Но разве мы не знаем, что LNP ? Кто-нибудь пытался доказать это? Опять же, каковы последние результаты или усилия на этом пути?

Может быть, я что-то упустил или искал неправильно, но я не смог найти никого, кто работал над вопросами L2P и LNP .

Леандро Затеско
источник
3
Я задал подмножество этого вопроса: cstheory.stackexchange.com/q/14159/4193
argentpepper
2
Мы не знаем разделения между и . Таким образом, любое строгое сдерживание среди классов между ними неизвестно. Плюс ли это @ argentpepper's Каковы последствия ? вопрос ответить на ваши вопросы? TC0NExpTimeL2P
Каве
3
Стив Кук со своими коллегами работает над подходом к отделению от . Я думаю, что это их последняя опубликованная работа: Стивен Кук, Пьер МакКензи, Дастин Вер, Марк Браверман, Рахул Сантанам, «Галька и разветвленные программы для оценки деревьев» , 2012.PL
Каве
4
@Kaveh Мы, конечно, знаем, что UNIFORM отличается от - ср. Нижняя граница схемы Аллендера для Перманента. (Униформа - это версия, которая имеет отношение к настоящему обсуждению.) Но да, даже отделение от униформы - открыто. TC0P#PTC0NPTC0
Райан Уильямс
@ Райан, ты прав, я думал о неоднородном , здесь важна унифицированная версия, как ты написал. TC0
Каве

Ответы:

12

Вы можете проверить следующую бумагу:

Трансляционные леммы, полиномиальное время и -пространство(logn)j Рональда В. Книга (1976).

Рисунки 1 и 2 в статье дают краткое изложение того, что известно, а что неизвестно.

Я положил теорему 3.10 в статье здесь:

  • DTIME(poly(n))DSPACE(poly(logn)) ;
  • для каждого , ;j1DTIME(nj)DSPACE(poly(logn))
  • для каждого , .j,k1DTIME(nj)DSPACE((logn)k)
Абузер Якарылмаз
источник
3
Бесплатная онлайн копия здесь .
Каве