Неизвестно, является ли или , где
- - это множество всех языков, разрешимых за полиномиальное время на детерминированной машине Тьюринга, и
- - это класс контекстно-зависимых языков, который, как известно, эквивалентен , языкам, выбранным с помощью линейно-ограниченных автоматов.
Для многих открытых вопросов существует тенденция к одному ответу ( а-ля "большинство экспертов считают, что "). Есть ли что-то подобное для этого вопроса?
В частности, будет ли любой ответ иметь неожиданные последствия? Я вижу только ожидаемые (но бездоказательные) последствия:
- Если , то (теорема о пространственной иерархии), следовательно, .
- Если , то есть язык и , следовательно , , следовательно , .
(Подтверждение: Юваль Фильмус указал на второе следствие этих двух явлений на /cs/69614/ ).