Как мы можем выразить «

9
  1. Как мы можем выразитьP=PSPACE"как формула первого порядка?
  2. Какой уровень арифметической иерархии содержит эту формулу (и каков в настоящее время известный минимальный уровень иерархии, которая ее содержит)?

Для справки, смотрите этот пост в блоге Lipton .

Марс
источник
1
кросс- пост
марс
1
Возможно, вы можете использовать то же доказательство Липтона, используя полную задачу PSPACE вместо SAT в определении ψ(x,c,y) и вы получите это PPSPACE можно выразить как x,cyψ(x,c,y) то есть это Π2приговор. Но ИМО это своего рода «хак» ... :-)
Марцио Де Биаси
3
Я бы поспорил на мою жизнь и все мирские вещи, которые вы можете представить как «Ложь». То есть это можно выразить даже в логике высказываний. :)
Shaull
3
@Shaull. Конечно. И как только вы покажете, что это правильное представление, вы сможете купить все необходимое вам имущество. Пожалуйста, не протестуйте, что место для комментариев слишком короткое, чтобы содержать доказательства.
Виджай Д
3
@VijayD - Я приму приманку: я нашел действительно замечательное доказательство, и места для комментариев достаточно. Но мне не нравится шрифт ...
Шал

Ответы:

25

Во-первых, я хочу обратиться к комментариям к вопросу, где было высказано предположение, что «ложь» выражает P=PSPACEпотому что утверждение является ложным. Хотя это может быть хорошей шуткой, на самом деле очень вредно так думать. Когда мы спрашиваем, как выразить определенное предложение в определенной формальной системе, мы не говорим о истинных ценностях. Если бы мы были, то когда кто-то спросил: «Как записать тот факт, что простых чисел бесконечно много?» мы могли бы ответить «3 + 3 = 6», но это явно не подойдет. По той же причине «ложь» не является правильным ответом на «как записать»P=PSPACE? ". Я думаю, что Фреге и Рассел изо всех сил пытались преподать нам этот урок. Хорошо, теперь ответ.

Позвольте мне показать, как выразить PSPACEP, другое направление аналогично, и тогда вы можете соединить их вместе, чтобы получить PSPACE=P, В любом случае, для ваших целей может быть достаточно выразитьPSPACEPв зависимости от того, что вы делаете.

Использование методов, аналогичных тем, которые используются при построении предиката Клини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,

Теперь рассмотрим формулу:

k,m.k,m.n.acceptspace(k,m,n)accepttime(k,m,n).
Это говорит о том, что для каждой машины k который использует самое большее пространство |n|m есть машина k который использует в большинстве случаев |n|m такой, что две машины принимают одинаково n«S. Другими словами, формула говоритPSPACEP, Эта формулаΠ30,

Мы можем улучшить это, если мы хотим вместо этого выразить предложение "TQBFнаходится в polytime ", что должно быть достаточно для большинства приложений, так как TQBF является завершенным PSPACE и поэтому его присутствие в polytime эквивалентноPSPACEP, Позволятьk0 быть (код) машиной, которая распознает TQBF в пространстве |n|m0, Затем "TQBFP«можно выразить как

k,m.n.acceptspace(k0,m0,n)accepttime(k,m,n).
Эта формула просто Σ20, Если бы я был теоретиком сложности, я бы знал, можно ли сделать еще лучше (но я сомневаюсь в этом).
Андрей Бауэр
источник
Ваш первый абзац почти как логическая, текстовая форма этого: xkcd.com/169
Виджай Д
21

Андрей уже объяснил, что P=PSPACE может быть написано как Σ20-приговор. Позвольте мне упомянуть, что эта классификация является оптимальной в том смысле, что если утверждение эквивалентноΠ20- значит, этот факт не релятивизируется. Точнее, набор оракуловA такой, что PA=PSPACEA определяется по Σ20формула со свободной переменной второго порядка A, но это не определяется ни одним Π20-формула. Аргумент изложен (дляP=NP, но это работает точно так же для PSPACE) в комментариях на /mathpro/57348 . (На самом деле, разработкой идеи можно показать, что множествоΣ20-полный в соответствующем смысле.)

РЕДАКТИРОВАТЬ: Топологическое доказательство, приведенное в связанном комментарии, короткое, но может показаться сложным. Вот прямой аргумент.

PAPSPACEA может быть написано как Π20формула формы ϕ(A)=xyθ(A,x,y), где θ является Δ00, Предположим для противоречия, чтоPA=PSPACEA также эквивалентно Π20-формулу ψ(A)=xzη(A,x,z), Исправить оракулыB, C такой, что PBPSPACEB а также PC=PSPACEC,

поскольку ϕ(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 numbers y0,y1,y2,, z0,z1,z2,, and finite partial oracles b0c0b1c1b2 such that

  1. θ(A,n,yn) for every oracle A extending bn,

  2. η(A,n,zn) for every oracle A extending cn.

Now, let A 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.

Emil Jeřábek
источник
3
Sad that such a nice answer is for a question that's now closed...
arnab