What is the complexity of this formula?

116 Views Asked by At

Keeping in mind the classification of (arithmetical) formulas in the arithmetical hierarchy, and given decidable predicates $P(x)$ and $Q(a,b,c)$, what is the complexity of

$\forall x P(x) \wedge \exists a \forall b \exists c Q(a,b,c)$?

My thinking is that, since the variables are independent, it could just as easily be $\Pi^0_4$:

$(\forall x \exists a \forall b \exists c [P(x) \wedge Q(a,b,c)])$

as it could be $\Sigma^0_4$:

$( \exists a \forall b \exists c \forall x[P(x) \wedge Q(a,b,c)])$,

but I can’t pick one.

1

There are 1 best solutions below

2
On BEST ANSWER

It is in fact guaranteed to be $\Sigma^0_3$. Remember that each arithmetical class is closed under (finite) conjunctions and disjunctions, and here the left conjunct is $\Pi^0_1$ hence a fortiori $\Sigma^0_3$ while the right conjunct is $\Sigma^0_3$.

To see this explicitly, note that the formula is equivalent to $$\exists a\forall b\forall x\exists c(P(x)\wedge Q(a,b,c)).$$

(And as usual you can avoid all syntactic manipulations entirely by using Shoenfield's limit lemma(s) to translate to a question about computational complexity; although that doesn't actually make things materially easier, it may be intuitively simpler - it was for me.)