The arithmetic hierarchy has a few different equivalent definitions but let's use one based on computability. We define inductively there hierarchies, Σ

_{i}

^{0}, Π

_{i}

^{0}and Δ

_{i}

^{0}. Σ

_{0}

^{0}=Π

_{0}

^{0}=Δ

_{0}

^{0}are the computable sets and

- Δ
_{i+1}^{0}are the sets computable with a Σ_{i}^{0}oracle. - Σ
_{i+1}^{0}are the sets computably enumerable with a Σ_{i}^{0}oracle. - Π
_{i}^{0}= co-Σ_{i}^{0}.

_{1}

^{0}are the computable sets and Σ

_{1}

^{0}are the computably enumerable sets. The halting problem is Σ

_{1}

^{0}-complete under computable reductions, the set of Turing machines that accepting infinite sets are Π

_{2}

^{0}-complete.

We completely know the structure of the arithmetic hierarchy, for i > 0, Σ

_{i}

^{0}≠ Π

_{i}

^{0}and for i ≥ 0, Δ

_{i}

^{0}= Σ

_{i+1}

^{0}∩ Π

_{i+1}

^{0}.

The arithmetic hierarchy inspired the polynomial-time hierarchy in complexity theory. Unlike the arithmetic hierarchy, separations in the polynomial-time hierarchy remain open and any separation implies P ≠ NP. While we have relativized worlds which do quite a few different separations and collapses in the polynomial-time hierarchy the following remains open: Does there exist a relativized world where the polynomial-time hierarchy looks like the arithmetic hierarchy, i.e., for i > 0, Σ

_{i}

^{p}≠ Π

_{i}

^{p}and for i ≥ 0, Δ

_{i}

^{p}= Σ

_{i+1}

^{p}∩ Π

_{i+1}

^{p}?

## No comments:

## Post a Comment