Большие классы, которые содержат LOGSPACE, для которых строгие включения неизвестны

На странице википедии на PSPACE упоминается, что включение не является строгим (к сожалению, без ссылок). $NL\subset PH$

Q1: А как насчет и - известны ли они как строгие? $L\subset PH$ $L\subset P^{\#P}$

Q2: Если нет, существует ли установленный класс который содержит и для которого неизвестно, является ли включение строгим? $C$ $P^{\#P}$ $L\subset C$

Q3: такие включения обсуждаются в литературе?

cc.complexity-theory complexity-classes logspace Лукаш Грабовски
источник

Я думаю, что для Q2 вы имеете в виду строго в PSPACE?

Сашо Николов

AFAIK, единственное известное разделение для

- это теорема о пространственной иерархии. Я не думаю, что известно, может ли какой-либо из классов, упомянутых в вопросе, моделировать супер-логарифмическое пространство, поэтому они также не известны как строгие. (Незнание разделения не является результатом, поэтому, вероятно, причина в отсутствии ссылок.)

L

$\mathsf{L}$

Каве

Даже для меньших классов, чем

, таких как равномерное

, включения Q1, как известно, не являются строгими. Я думаю, учитывая текущее состояние знаний, практически любой класс

между

и строго содержащимися в

является положительным ответом на вопрос Q2.

L

$\mathsf{L}$

{N C}^{1}

$\mathsf{NC}^1$

C

$C$

P^{# P}

$\mathsf{P}^{\mathsf{\# P}}$

P S P A C E

$\mathsf{PSPACE}$

Джошуа Грохов

В заголовке вашего вопроса написано «Самый большой класс». Разве вы не имеете в виду "самый маленький класс"?

Шал

Даже неизвестно, включен ли

в PH.

строго содержит TC ^ 0 в качестве аргумента иерархии, но, как уже упоминал Джошуа Грохов, это не известно для NC ^ 1. Для Q2 вы можете взять CH.

A C^{0} [6]

$AC^0[6]$

P^{# P}

$P^{\#P}$

Эмиль Йержабек

Ответы:

Это мой любимый вопрос.

В своей статье «Компромисс между пространством и временем для удовлетворения» Фортнау показал, что правильно содержится в , где - любая неограниченная функция. То есть, недетерминирован logspace правильно содержится в чередующихся полиномиальное время с чередований. $NL$ $\Sigma_{a(n)} P$ $a(n)$ $a(n)$

Показано , что не в для фиксированного постоянной означало бы , что . (Чтобы увидеть это, рассмотрим противозачаточное.) $NL$ $\Sigma_k P$ $k$ $NL \neq NP$

Он открыт ли . В последний раз, когда я серьезно пытался доказать это, это привело к статье "Пространство во времени для подсчета решений NP по модулю целых чисел" . Я пытался найти какую-то симуляцию для каждого языка в лог-пространстве, которая потребовала бы времени для некоторого фиксированного когда у человека есть доступ к оракулу для подсчета удовлетворяющих заданий для данной формулы. (Это подразумевает $NL = P^{\#P}$ $n^k$ $k$ $LOGSPACE \neq P^{\#P}$ .) Мой подход не сработал, но в итоге я использовал тот же подход для доказательства пространственно-временных нижних границ для решения и других связанных результатов. $Mod_6 SAT$

Uniform- правильно содержится в . Доказательство в Allender, «Постоянный требует больших равномерных пороговых цепей» . Любое улучшение в этом разделении открыто. (Например, проверка формы - открыта, и проверка формы - также открыта.) $TC^0$ $P^{\#P}$ $NC^1 \neq P^{\#P}$ $TC^0 \neq NP$

Райан Уильямс
источник

T C

$\mathsf{TC}$

o (\log \log n)

$o(\log \log n)$

Да, я знаю и об этом, и о других ссылках. Но я придерживался краткого ответа, который не занял бы больше 10 минут, чтобы написать.

Райан Уильямс