On Equivalent Characterizations of the Polynomial Hierarchy in Abstract Models of Computation

Abstract

We investigate machine models similar to Turing machines that are augmented with the operations of a first-order structure $\mathcal{R}$, and we show that under weak conditions on $\mathcal{R}$, the complexity class ${\Sigma }_k\mathcal{R}$ may be characterized in four equivalent ways: (1) by polynomial-time algorithms implemented on $\mathcal{R}$-machines together with witness strings, (2) by the ${\Sigma }_k\mathcal{R}$-complete problem ${\Sigma }_k\text{SAT}(\mathcal{R})$, (3) by the $k$th existential fragment of second-order metafinite logic over $\mathcal{R}$ via descriptive complexity, and (4) via oracles. By characterizing ${\Sigma }_k\mathcal{R}$ in these four ways, we extend previous work and embed it in one coherent framework. In addition, we derive similar results for ${\exists }_k\mathcal{R}$, the constant-free Boolean part of ${\Sigma }_k\mathcal{R}$, by showing that ${\exists }_k\mathcal{R}$ may be characterized in four analogous ways. Some conditions on $\mathcal{R}$ must be assumed in order to achieve the above quaternity because there are infinite-vocabulary structures for which $\text{NP}(\mathcal{R})={\Sigma }_1\mathcal{R}$ does not have a complete problem. Surprisingly, even in these cases, we show that $\text{NP}(\mathcal{R})$ does have a characterization in terms of existential second-order metafinite logic, suggesting that descriptive complexity theory is well suited to working with infinite-vocabulary structures, such as real vector spaces.

79 pages, 4 figures