Можно ли использовать описательную версию сложности теоремы Райса для разделения AC0 и PSPACE?

10

В этом вопросе было отмечено, что существуют версии описательной сложности теоремы Райса. Я нашел доказательство следующей теоремы:

Учитывая класс сложности C , нетривиальные свойства языков в C не могут быть вычислены в C

Ранее я опубликовал найденное мной доказательство, но поскольку оно было очень длинным и в комментариях было указано, что в этой статье уже есть доказательство этой теоремы, я удалил его. (Если по какой-либо причине вы отчаянно нуждаетесь в моих доказательствах, пожалуйста, посмотрите предыдущие редакции этого вопроса.)

Меня интересует, можно ли использовать эту теорему для разделения AC0 и PSPACE. Вот аргумент:

Рассмотрим свойство P класса сложности AC0, определенное следующим образом:

P : свойство быть FO-запросом, который принимает определенную фиксированную структуру, а именно структуру, состоящую из одного элемента, без функций, без констант и без отношений

Ясно, что по приведенной выше теореме P не разрешима в AC0; это нетривиальное свойство запросов FO.

Однако небольшое исследование должно показать, что вычисление того, принимает ли запрос FO такую ​​простую структуру или нет, может быть решено так же легко, как и TQBF; таким образом, P разрешимо в PSPACE.

Чтобы обеспечить ясность в этом вопросе (что P вычислимо в PSPACE): обратите внимание, что интересующее нас свойство требует, чтобы структура была FO. Итак, мы пытаемся определить, принимает ли запрос FO, который выполняется в одноэлементной структуре без отношений. Поскольку нет отношений, с которыми нужно иметь дело, должно быть ясно, что задача решения такого запроса FO эквивалентна решению экземпляра TQBF; нет никаких отношений, поэтому единственная проблема, которая остается, состоит в том, чтобы оценить, верна ли количественная булева формула. Это в основном просто TQBF, так что P вычислимо в PSPACE.

Поскольку P вычислимо в PSPACE, но не AC0, мы должны сделать вывод, что AC0! = PSPACE. Правильно ли это рассуждение или я где-то допустил ошибку? Я особенно обеспокоен предыдущим пунктом; Я постараюсь уточнить и обновить аргумент завтра после того, как у меня будет возможность немного больше подумать об экспозиции.

В качестве ответа я бы принял пример запроса FO, который при расчете на описанной выше одноэлементной, не связанной с отношениями структуре явно не имеет смысла в качестве примера TQBF. (Я полагаю, что его нет, поэтому, если вы покажете, что он есть, это будет контрпример.)

Спасибо.

Филип Уайт
источник
@Kaveh: Вы должны сделать свой комментарий ответом.
Дай Ле
@Kaveh: Спасибо за ваш комментарий. Я немного смущен тем, что вы говорите, хотя. На какую машину в PSPACE для наборов AC0 вы ссылались? Я имел в виду свойство P, которое относится конкретно к запросам FO по очень простым структурам. Я полагаю, что для оценки того, принимает ли FO-запрос простую структуру, гарантированно будет TQBF, то есть PSPACE. Я не вижу, где нужен универсальный симулятор для AC0.
Филипп Уайт
@Kaveh: ОК. Я подготовлю свои попытки доказательства гипотезы в этом вопросе и опубликую их как отдельный вопрос. Я думал, что это правильно, но я часто ошибаюсь. (Конечно, если вы опровергаете мою гипотезу до этого, я не буду беспокоиться.)
Филипп Уайт
Ой. Я просто отправил это как вопрос. Должен ли я удалить новый вопрос и опубликовать его как ответ?
Филипп Уайт
(Я удалил это и добавил это к этому вопросу.)
Филип Уайт

Ответы:

7

Определение нетривиальных свойств наборов (индексация) в классе сложности так же сложно, как вычисление графика универсальной функции для класса. Интуитивно это означает, что единственный способ определить нетривиальное свойство - это смоделировать машины и ждать ответов. Мне кажется, что идея использования такого свойства даст только то, что известно из теорем иерархии. (Подробности см. В теореме 4.2 Д. Козена « Индексация субрекурсивных классов », 1978 г. и точное утверждение теоремы.)

грUAС0AС0пSпaсеAС0LLпSпaсеAС0AС0FОпSпaсепSпaсеAС0AС0пSaпсе

AС0LпSпaсе

Кава
источник
Интересно, спасибо. Итак, вы говорите: 1) Мой аргумент был прав, но 2) Был более легкий путь. :) Думаю, мне нужно освежить теорему о пространственной иерархии.
Филипп Уайт
FО
Каве
Ок, отлично. Я на самом деле только что проверил определение FO. Я знал, что это включало символ равенства; Вот почему я требовал, чтобы структура была только одним элементом. Таким образом, любое утверждение о равенстве двух переменных не повлияет на истинность запроса.
Филипп Уайт
Еще один комментарий ... вы сделали важный вывод о нелогических символах. Поскольку нет никаких отношений, символ равенства фактически необходим. В частности, необходимо выразить очень логические литералы, которые необходимы для выражения TQBF.
Филипп Уайт
FО также содержит отношения для порядка, сложения, умножения и бита (хотя некоторые из них можно определить из других).
Каве