Я изучаю проблему, которая трудна для класса количественных логических формул с логарифмическим числом чередований кванторов. Проблема в этом классе будет выглядеть так:
Там , где журнал п = п , а Р представляет собой логическая формула переменных х 1 ... х п .
Этот класс , очевидно , содержит и содержится в A P = P S P A C E . Есть ли название для этого класса? Что-нибудь еще известно об этом?
Ответы:
Опираясь на ответ Майкла Wehar, это , кажется , что вы можете легко показать , что вычисления могут быть закодированы в polysize таких QBFs: вы используете O ( журнал п ) чередования, каждый из p o l y ( n ) битов, и сделать аргумент, аналогичный теореме Савича. Каждые два чередований будут делить время выполнения вычислений с помощью р O л у ( пNTISP(nlogn,poly(n)) O(logn) poly(n) фактор.poly(n)
Я бы назвал класс , следуя нотации в Fortnow «Компромисс между пространством и временем для удовлетворения», который также можно было бы привести в качестве аргумента, изложенного в предыдущем абзаце (но, пожалуйста, см. Статью для более ранних ссылок).ΣO(logn)P
источник
(1) Что мы уже знаем:
Как вы уже заявили, QBF с чередованием квантификаторов труден для каждого уровня полиномиальной иерархии.log(n)
(2) Я думаю, что мы также можем доказать следующее:
Проблема состоит в -Жесткий.NSPACE(log2(n))
(3) Вот мое неофициальное обоснование предыдущего утверждения:
Учитывая пространство связанно НТМ и строка ввода, нам нужно , чтобы определить , существует ли принимающие вычисления на данной строке ввода.log2(n)
Каждая конфигурация в вычислении может быть представлена по существу битами. Другими словами, мы можем представить конфигурацию группой переменных log 2 ( n ) .log2(n) log2(n)
Идея состоит в том, что у нас есть начальная конфигурация и конечная конфигурация, и нам нужно угадать вычисления, которые происходят между ними. Мы рекурсивно угадываем «средние» конфигурации с использованием существующих квантификаторов и рекурсивно проверяем, что «левая» конфигурация переходит в «среднюю», а «средняя» конфигурация переходит в «правую», используя для всех квантификаторов.
Теперь, чтобы сделать эту работу, вместо того, чтобы выбирать одну «среднюю» конфигурацию, нам нужно выбрать группу одинаково расположенных «промежуточных» конфигураций между «левой» и «правой» конфигурациями. В частности, мы могли бы догадаться "промежуточных" конфигураций с равным интервалом, используя существующие квантификаторы с √n−−√ переменных, а затем рекурсивно вычислять каждый разрыв между конфигурациями, используя для всех квантификаторов с примерноlog(n)переменными.n−−√∗log2(n) log(n)
Рекурсия должна продолжаться только до глубины чтобы иметь возможность охватить вычисление длины √2∗log(n) где каждая конфигурация имеет не болееlog2(n)много битов.n−−√2∗log(n)=nlog(n)=2log2(n) log2(n)
Поскольку рекурсия имеет глубину , у нас есть только O ( log ( n ) ) групп переменных, то есть чередований. Поскольку каждая группа квантификаторов имеет только √O(log(n)) O(log(n)) переменных, всего имеемO( √n−−√∗log2(n) переменных.O(n−−√∗log3(n))
Не стесняйтесь предлагать любые отзывы или исправления. Большое спасибо, и я надеюсь, что это поможет немного.
(4) Более общее утверждение, предложенное ответом Райана:
Вы должны быть в состоянии выполнить предыдущую конструкцию в более общем виде. Учтите следующее:
На каждом шаге рекурсии разбейте на групп «промежуточных» конфигураций, используя c ( n ) битов на конфигурацию. Затем выполните рекурсию на глубину d ( n ) .g(n) c(n) d(n)
Пока у нас не слишком много переменных и слишком много чередований, это, кажется, работает нормально. Грубо говоря, нам нужно следующее:
Наш обобщенный подход будет использоваться для моделирования недетерминированных машин Тьюринга, которые выполняются за шагов с использованием c ( n ) битов памяти.g(n)d(n) c(n)
В частности, мы выбираем следующее:
Предыдущие неравенства выполняются, и мы можем выполнить построение для моделирования недетерминированных машин Тьюринга, которые работают примерно за шагов, используя √2log2(n) бит памяти.n√2∗log2n
Другими словами, у нас результат лучше, чем раньше. В частности, проблема сложна для .NTISP(2log2(n),n√2∗log2n)
(5) Дальнейшие обобщения:
В предыдущем обобщении мы моделировали недетерминированные ограниченные временем и пространством машины Тьюринга. Тем не менее, мы также можем моделировать чередующиеся ограниченные временем и пространством машины Тьюринга.
Позвольте мне объяснить немного. Таким образом, мы используем примерно чередования для рекурсии в глубину log ( n ) . Тем не менее, мы могли бы использовать некоторые из чередований, скажем, √log(n) log(n) . Тогда мы могли бы использовать оставшиеся √log(n)−−−−−√ чередования идти в глубину √log(n)−−−−−√ .log(n)−−−−−√
В этом случае мы могли бы смоделировать чередующиеся машины Тьюринга, которые имеют чередований с сублинейными длинами свидетелей, пробег для2 log 3log(n)−−−−−√ шагов и используйте√2log32(n) бит памяти.n√2∗log2n
Другими словами, проблема трудна для с сублинейными длинами свидетелей. Кроме того, этот класс может быть написан с использованиемнотацииSTA,упомянутой в комментариях выше.AltTimeSpace(log(n)−−−−−√,2log32(n),n√2∗log2n) STA
Спасибо за комментарии и не стесняйтесь предлагать любые дальнейшие исправления или разъяснения. :)
источник
Короче ответ.
See my longer answer for more details on the trade-offs betweena(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 fromn 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.
источник