Количественные булевы формулы с логарифмическими чередованиями

15

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

(x1,x2,xa1)(xa1+1,xa2),(xalogn1,xaжурналN)F

Там , где журнал п = п , а Р представляет собой логическая формула переменных х 1 ... х п .aжурналNзнак равноNFИкс1...ИксN

Этот класс , очевидно , содержит и содержится в A P = P S P A C E . Есть ли название для этого класса? Что-нибудь еще известно об этом?пЧАСAпзнак равнопSпAСЕ

isaacg
источник
3
Ну, это завершено для чередования полиномиального времени с логарифмически много чередований.
Эмиль Йержабек поддерживает Монику
2
Согласованным обозначением для класса сложности этой задачи будет STA ( ). Здесь STA (s (n), t (n), a (n)) - это мера чередования пространства-времени, введенная Берманом в «Сложность логических теорий», появившаяся в TCS в 1980 году. Этот класс содержит все решения проблема разрешима с помощью чередующейся машины Тьюринга за время t (n) с использованием пространства s (n) и чередованием не более a (n) раз в каждой ветви вычислений. Как указал Эмиль, ваша задача должна быть завершена для этого класса. ,nO(1),O(logn)
Кристоф Хаазе
2
AltTime (LG N, Poly (N))
Каве
Разве это также не бинарный аналог класса FOLL, представленный Баррингтоном, Кадау, Маккензи и Ланге. FOLL определяется путем итерации блока FO, в основном n-входной, n-выходной равномерной схемы AC0 loglog n раз. Он слишком слаб для вычисления четности, но неизвестно, что он содержится в классе, меньшем чем AC ^ 1. Он может выполнять ряд нетривиальных задач, включая включение в коммутативную группу, представленную в виде таблицы умножения. Я хотел бы назвать рассматриваемый класс PHL, поскольку он соответствует итерационному журналу блока PH n раз. Я думаю, что до сих пор не ясно, сопоставимо ли это с PSPACE.
SamiD
Также, если абелева группа задается схемой, которая принимает на вход два n-битных числа и выводит n-битное число, то включение в PHL осуществляется с помощью доказательства, аналогичного Barrington и др. Выше.
SamiD

Ответы:

7

Опираясь на ответ Майкла Wehar, это , кажется , что вы можете легко показать , что вычисления могут быть закодированы в polysize таких QBFs: вы используете O ( журнал п ) чередования, каждый из p o l y ( n ) битов, и сделать аргумент, аналогичный теореме Савича. Каждые два чередований будут делить время выполнения вычислений с помощью р O л у ( пNTISP(nlogn,poly(n))O(logn)poly(n) фактор.poly(n)

Я бы назвал класс , следуя нотации в Fortnow «Компромисс между пространством и временем для удовлетворения», который также можно было бы привести в качестве аргумента, изложенного в предыдущем абзаце (но, пожалуйста, см. Статью для более ранних ссылок).ΣO(logn)P

Райан Уильямс
источник
Большое спасибо за комментарий и последующий ответ. Я отредактировал свой ответ и добавил подробности обобщения аргумента. На самом деле существует компромисс между временем, пространством и чередованием для вычислений, которые могут быть закодированы.
Майкл Вехар
Спасибо за добавленную ссылку! Кроме того, я добавил более краткий ответ, чтобы, надеюсь, уточнить. Еще раз спасибо. :)
Майкл Вехар
7

(1) Что мы уже знаем:

Как вы уже заявили, QBF с чередованием квантификаторов труден для каждого уровня полиномиальной иерархии.log(n)

(2) Я думаю, что мы также можем доказать следующее:

Проблема состоит в -Жесткий.NSPACE(log2(n))

(3) Вот мое неофициальное обоснование предыдущего утверждения:

Учитывая пространство связанно НТМ и строка ввода, нам нужно , чтобы определить , существует ли принимающие вычисления на данной строке ввода.log2(n)

Каждая конфигурация в вычислении может быть представлена ​​по существу битами. Другими словами, мы можем представить конфигурацию группой переменных log 2 ( n ) .log2(n)log2(n)

Идея состоит в том, что у нас есть начальная конфигурация и конечная конфигурация, и нам нужно угадать вычисления, которые происходят между ними. Мы рекурсивно угадываем «средние» конфигурации с использованием существующих квантификаторов и рекурсивно проверяем, что «левая» конфигурация переходит в «среднюю», а «средняя» конфигурация переходит в «правую», используя для всех квантификаторов.

Теперь, чтобы сделать эту работу, вместо того, чтобы выбирать одну «среднюю» конфигурацию, нам нужно выбрать группу одинаково расположенных «промежуточных» конфигураций между «левой» и «правой» конфигурациями. В частности, мы могли бы догадаться "промежуточных" конфигураций с равным интервалом, используя существующие квантификаторы сnпеременных, а затем рекурсивно вычислять каждый разрыв между конфигурациями, используя для всех квантификаторов с примерноlog(n)переменными.nlog2(n)log(n)

Рекурсия должна продолжаться только до глубины чтобы иметь возможность охватить вычисление длины 2log(n)где каждая конфигурация имеет не болееlog2(n)много битов.n2log(n)=nlog(n)=2log2(n)log2(n)

Поскольку рекурсия имеет глубину , у нас есть только O ( log ( n ) ) групп переменных, то есть чередований. Поскольку каждая группа квантификаторов имеет только O(log(n))O(log(n))переменных, всего имеемO(nlog2(n)переменных.O(nlog3(n))

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

(4) Более общее утверждение, предложенное ответом Райана:

Вы должны быть в состоянии выполнить предыдущую конструкцию в более общем виде. Учтите следующее:

На каждом шаге рекурсии разбейте на групп «промежуточных» конфигураций, используя c ( n ) битов на конфигурацию. Затем выполните рекурсию на глубину d ( n ) .g(n)c(n)d(n)

Пока у нас не слишком много переменных и слишком много чередований, это, кажется, работает нормально. Грубо говоря, нам нужно следующее:

  • g(n)c(n)d(n)n
  • d(n)log(n)

Наш обобщенный подход будет использоваться для моделирования недетерминированных машин Тьюринга, которые выполняются за шагов с использованием c ( n ) битов памяти.g(n)d(n)c(n)

В частности, мы выбираем следующее:

  • g(n)=n

  • c(n)=n2log2n

  • d(n)=2log2(n)

Предыдущие неравенства выполняются, и мы можем выполнить построение для моделирования недетерминированных машин Тьюринга, которые работают примерно за шагов, используя 2log2(n) бит памяти.n2log2n

Другими словами, у нас результат лучше, чем раньше. В частности, проблема сложна для .NTISP(2log2(n),n2log2n)

(5) Дальнейшие обобщения:

В предыдущем обобщении мы моделировали недетерминированные ограниченные временем и пространством машины Тьюринга. Тем не менее, мы также можем моделировать чередующиеся ограниченные временем и пространством машины Тьюринга.

Позвольте мне объяснить немного. Таким образом, мы используем примерно чередования для рекурсии в глубину log ( n ) . Тем не менее, мы могли бы использовать некоторые из чередований, скажем, log(n)log(n) . Тогда мы могли бы использовать оставшиесяlog(n) чередования идти в глубинуlog(n) .log(n)

В этом случае мы могли бы смоделировать чередующиеся машины Тьюринга, которые имеют чередований с сублинейными длинами свидетелей, пробег для2 log 3log(n)шагов и используйте2log32(n) бит памяти.n2log2n

Другими словами, проблема трудна для с сублинейными длинами свидетелей. Кроме того, этот класс может быть написан с использованиемнотацииSTA,упомянутой в комментариях выше.AltTimeSpace(log(n),2log32(n),n2log2n)STA

Спасибо за комментарии и не стесняйтесь предлагать любые дальнейшие исправления или разъяснения. :)

Майкл Вехар
источник
1
Разве -твердость не будет следовать сразу же за PH-твердостью? NL2
Нихилу
1
2kk
1
NL2PHNL2
1
@MichaelWehar Ой. Конечно ты прав! Смежный вопрос здесь: cstheory.stackexchange.com/questions/14159/...
Нихилу
2
Почему нет NTяSп(NжурналN,поLY(N))-жесткий?
Райан Уильямс
1

Короче ответ.

Начальные наблюдения:

  • Проблема сложна для каждого уровня полиномиальной иерархии.
  • Проблема чередуется с чередующимися машинами Тьюринга с журнал(N) чередования, которые бегут в течение полиномиального времени.

Более глубокое понимание:

  • Предложенный выше комментарием Каве, проблема может закодировать вычисления для ALTTяме(журнал(N),N) Машины Тьюринга.
  • Кроме того, как указал Райан, проблема может закодировать вычисления для NTямеSпaсе(2журнал2(N),N) Машины Тьюринга.
  • В более общем плане, проблема может закодировать вычисления для машин, соответствующих различным классам вида AltTimeSpace(a(n),t(n),s(n)) with restricted witness lengths. I'm not quite sure what the exact relationship between a(n), t(n), and s(n) has to be, but we know that:

    1. a(n)log(n)

    2. t(n)2log2(n)

    3. s(n)n

See my longer answer for more details on the trade-offs between a(n), t(n), and s(n).

Note: In the above, when I say encode computations, I mean encode the computation without blowing up the instance size too much. That is, if we blow-up from n size Turing machine input to poly(n) size formula, then I think that although the blow-up is polynomial, it is good to pay close attention to the degree of the polynomial. The reason for the semi-fine-grained perspective is to try and slightly better recognize how the different complexity measures a(n), t(n), and s(n) depend on each other.

Michael Wehar
источник
Also, there is another factor that I omitted. That is, the witness size used with each alternation takes up variables. In other words, the larger the witnesses, the fewer variables that we have meaning that potentially we can't represent as many bits per configuration causing us to possibly require there to be less space for the machine that we encode computations for.
Michael Wehar
Basically, all witness lengths for the quantifiers are sublinear and how large we can make them depends on the choice of a(n), t(n), and s(n).
Michael Wehar
Maybe an inner most there exists quantifier doesn't need to have restricted witness size because we can guess as we go.
Michael Wehar