Friday, November 01, 2013

Andrzej Mostowski (1913-1975)

Andrzej Mostowski was born 100 years ago today. While Mostowski worked in many areas of logic, including early fundamental work on model theory, for our readers he's best known for co-discovering the arithmetic hierarchy, sometimes called the Kleene-Mostowski hierarchy.

The arithmetic hierarchy has a few different equivalent definitions but let's use one based on computability. We define inductively there hierarchies, Σi0, Πi0 and Δi0. Σ000000 are the computable sets and
  1. Δi+10 are the sets computable with a Σi0 oracle.
  2. Σi+10 are the sets computably enumerable with a Σi0 oracle.
  3. Πi0 = co-Σi0.
In particular, Δ10 are the computable sets and Σ10 are the computably enumerable sets. The halting problem is Σ10-complete under computable reductions, the set of Turing machines that accepting infinite sets are Π20-complete.

We completely know the structure of the arithmetic hierarchy, for i > 0, Σi0 ≠ Πi0 and for i ≥ 0, Δi0 = Σi+10 ∩ Πi+10.

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, Σip ≠ Πip and for i ≥ 0, Δip = Σi+1p ∩ Πi+1p?

No comments:

Post a Comment