Laboratoire de l'Informatique et du Parallélisme » Linear Arithmetic

%(include closure properties)

\begin{definition}

Given $i\geq 0$, a  language $L$ belongs to the class $\sigp{i}$ off there exists a polynomial time predicate $A$ and a polynomial $q$ such that:

$$ x \in L \Leftrightarrow \exists y_1 \in \{0,1\}^{q(\size{x})}\forall y_2 \in \{0,1\}^{q(\size{x})}\dots Q_iy_i\in \{0,1\}^{q(\size{x})}\ A(x,y_1,\dots,y_i)=1$$

where $Q_i=\forall$ (resp. $Q_i=\exists$) if $i$ is even (resp. odd).

The class $\pip{i}$ is defined similarly but with first quantifier $\forall$ instead of $\exists$. 

\end{definition}

In particular: $\sigp{0}=\pip{0}=\ptime$, $\sigp{1}=\np$, $\pip{1}=\conp$.

The polynomial hierarchy is defined as $\ph:=\cup_i \sigp{i}$, and we also have $\ph=\cup_i \pip{i}$.

Given a language $L$ we denote as $\fptime(L)$ the class of functions computable by a deterministic

polynomial time Turing machine with oracle $L$.

We now define the following function classes:

\begin{eqnarray*}

 \fphi{i+1} &= & \fptime(\sigp{i}),\\

 \fph &=& \cup_i  \fphi{i}. 

\end{eqnarray*}

One can then check that $ \fphi{i+1} =  \fptime(\pip{i})=  \fptime(\sigp{i}\cup \pip{i})$.

\newcommand{\sigp}[1]{\Sigma^p_{#1}}

\newcommand{\pip}[1]{\Pi^p_{#1}}

	\newcommand{\np}{\mathbf{NP}}

	\newcommand{\conp}{\mathbf{coNP}}