- Как мы можем выразить"как формула первого порядка?
- Какой уровень арифметической иерархии содержит эту формулу (и каков в настоящее время известный минимальный уровень иерархии, которая ее содержит)?
Для справки, смотрите этот пост в блоге Lipton .
Для справки, смотрите этот пост в блоге Lipton .
Ответы:
Во-первых, я хочу обратиться к комментариям к вопросу, где было высказано предположение, что «ложь» выражаетP=PSPACE потому что утверждение является ложным. Хотя это может быть хорошей шуткой, на самом деле очень вредно так думать. Когда мы спрашиваем, как выразить определенное предложение в определенной формальной системе, мы не говорим о истинных ценностях. Если бы мы были, то когда кто-то спросил: «Как записать тот факт, что простых чисел бесконечно много?» мы могли бы ответить «3 + 3 = 6», но это явно не подойдет. По той же причине «ложь» не является правильным ответом на «как записать»P=PSPACE ? ". Я думаю, что Фреге и Рассел изо всех сил пытались преподать нам этот урок. Хорошо, теперь ответ.
Позвольте мне показать, как выразитьPSPACE⊆P , другое направление аналогично, и тогда вы можете соединить их вместе, чтобы получить PSPACE=P , В любом случае, для ваших целей может быть достаточно выразитьPSPACE⊆P в зависимости от того, что вы делаете.
Использование методов, аналогичных тем, которые используются при построении предиката КлиниT можно построить формулу ограниченного квантора acceptspace(k,m,n) (который, таким образом, проживает в Σ00=Π00 ) говоря "когда мы запускаем машину, закодированную k и ограничил свое использование пространства |n|m , машина принимает ввод n ." Вот |n| длина n , Неформальный способ увидеть, что такие формулы существуют:k , m , а также n мы можем вычислить примитивную рекурсивную границу для того, сколько времени и места нам понадобится (т.е. самое большее |n|m пространство и самое большее 2|n|m время). Затем мы просто ищем все возможные трассы выполнения, которые находятся в пределах вычисляемых границ - такой поиск довольно неэффективен, но он примитивно рекурсивен и поэтому мы можем выразить его как ограниченную формулу.
Есть похожая формулаaccepttime(k,m,n) в котором время выполнения связано |n|m ,
Теперь рассмотрим формулу:
Мы можем улучшить это, если мы хотим вместо этого выразить предложение "TQBF находится в polytime ", что должно быть достаточно для большинства приложений, так как TQBF является завершенным PSPACE и поэтому его присутствие в polytime эквивалентноPSPACE⊆P , Позволятьk0 быть (код) машиной, которая распознает TQBF в пространстве |n|m0 , Затем "TQBF∈P «можно выразить как
источник
Андрей уже объяснил, чтоP=PSPACE может быть написано как Σ02 -приговор. Позвольте мне упомянуть, что эта классификация является оптимальной в том смысле, что если утверждение эквивалентноΠ02 - значит, этот факт не релятивизируется. Точнее, набор оракуловA такой, что PA=PSPACEA определяется по Σ02 формула со свободной переменной второго порядка A , но это не определяется ни одним Π02 -формула. Аргумент изложен (дляP=NP , но это работает точно так же для PSPACE ) в комментариях на /mathpro/57348 . (На самом деле, разработкой идеи можно показать, что множествоΣ02 -полный в соответствующем смысле.)
РЕДАКТИРОВАТЬ: Топологическое доказательство, приведенное в связанном комментарии, короткое, но может показаться сложным. Вот прямой аргумент.
посколькуϕ(B) , Существует y0 такой, что θ(B,0,y0) , Однако,θ является ограниченной формулой, следовательно, оценка истинности значения θ(B,0,y0) использует только конечную часть оракула. Таким образом, существует конечная частьb0 из B такой, что θ(A,0,y0) за каждого оракула A простирающийся b0 ,
ПозволятьC[b0] обозначить оракула, который распространяется b0 , and agrees with C where b0 is undefined. Since PA and PSPACEA are unaffected by a finite change in the oracle, we have ψ(C[b0]) . By the same argument as above, there exists z0 and a finite part c0 of C[b0] such that η(A,0,z0) for every A extending c0 . We may assume that c0 extends b0 .
Continuing in the same fashion, we construct infinite sequences of numbersy0,y1,y2,… , z0,z1,z2,… , and finite partial oracles b0⊆c0⊆b1⊆c1⊆b2⊆⋯ such that
Now, letA be an oracle which extends all bn and cn . Then 1 and 2 imply that ϕ(A) and ψ(A) simultaneously hold, which contradicts the assumption that they are complements of each other.
источник