Какова предполагаемая связь между языками P (PTime) и Type 1 (контекстно-зависимыми)?

10

Неизвестно, является ли или , гдеPCSLPCSL

  • P - это множество всех языков, разрешимых за полиномиальное время на детерминированной машине Тьюринга, и
  • CSL - это класс контекстно-зависимых языков, который, как известно, эквивалентен NSPACE(O(n)) , языкам, выбранным с помощью линейно-ограниченных автоматов.

Для многих открытых вопросов существует тенденция к одному ответу ( а-ля "большинство экспертов считают, что PNP "). Есть ли что-то подобное для этого вопроса?

В частности, будет ли любой ответ иметь неожиданные последствия? Я вижу только ожидаемые (но бездоказательные) последствия:

  • Если PCSL , то PNSPACE(O(n))NSPACE(O(n2)) (теорема о пространственной иерархии), следовательно, PPSpace .
  • Если PCSL , то есть язык lPNSPACE(O(n)) и , следовательно , lPNL , следовательно , NLP .

(Подтверждение: Юваль Фильмус указал на второе следствие этих двух явлений на /cs/69614/ ).

MAK
источник

Ответы:

12

Если , то . По аргументу заполнения это подразумевает для каждой суперполиномиальной функции хорошего поведения и каждый . Я считаю, что такое сильное преимущество пространства во времени не должно быть правдой. Лучший на данный момент известный результат в этом направлении - это благодаря Хопкрофту, Полу и Валианту.PCSLPDSPACE(n2)

DTIME(t(n))DSPACE(t(n)ϵ)
t(n)ϵ>0
DTIME(t(n))DSPACE(t(n)/logt(n)),
Эмиль Йержабек
источник
Спасибо, я принял этот ответ сейчас, хотя, учитывая природу этого вопроса, дальнейшие ответы, конечно, все же будут приветствоваться.
Мак