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

12

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

Q1: А как насчет и L P # P - известны ли они как строгие?LPHLP#P

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

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

Лукаш Грабовски
источник
2
Я думаю, что для Q2 вы имеете в виду строго в PSPACE?
Сашо Николов
5
AFAIK, единственное известное разделение для - это теорема о пространственной иерархии. Я не думаю, что известно, может ли какой-либо из классов, упомянутых в вопросе, моделировать супер-логарифмическое пространство, поэтому они также не известны как строгие. (Незнание разделения не является результатом, поэтому, вероятно, причина в отсутствии ссылок.)L
Каве
4
Даже для меньших классов, чем , таких как равномерное N C 1 , включения Q1, как известно, не являются строгими. Я думаю, учитывая текущее состояние знаний, практически любой класс C между P # P и строго содержащимися в P S P A C E является положительным ответом на вопрос Q2. LNC1CP#PPSPACE
Джошуа Грохов
В заголовке вашего вопроса написано «Самый большой класс». Разве вы не имеете в виду "самый маленький класс"?
Шал
4
Даже неизвестно, включен ли в PH. P # P строго содержит TC ^ 0 в качестве аргумента иерархии, но, как уже упоминал Джошуа Грохов, это не известно для NC ^ 1. Для Q2 вы можете взять CH. AC0[6]P#P
Эмиль Йержабек

Ответы:

7

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

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

Показано , что не в Е K P для фиксированного постоянной к означало бы , что N L N P . (Чтобы увидеть это, рассмотрим противозачаточное.)NLΣkPkNLNP

Он открыт ли . В последний раз, когда я серьезно пытался доказать это, это привело к статье "Пространство во времени для подсчета решений NP по модулю целых чисел" . Я пытался найти какую-то симуляцию для каждого языка в лог-пространстве, которая потребовала бы n k времени для некоторого фиксированного k, когда у человека есть доступ к оракулу для подсчета удовлетворяющих заданий для данной формулы. (Это подразумевает L O G S P A C E P # PNL=P#PnkkLOGSPACEP#P.) Мой подход не сработал, но в итоге я использовал тот же подход для доказательства пространственно-временных нижних границ для решения и других связанных результатов.Mod6SAT

Uniform- правильно содержится в Р # Р . Доказательство в Allender, «Постоянный требует больших равномерных пороговых цепей» . Любое улучшение в этом разделении открыто. (Например, проверка формы - N C 1P # P открыта, и проверка формы - T C 0N P также открыта.)TC0P#PNC1P#PTC0NP

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