Révision 163 CSL17/preliminaries.tex
| preliminaries.tex (revision 163) | ||
|---|---|---|
| 8 | 8 |
%(include closure properties) |
| 9 | 9 |
|
| 10 | 10 |
\begin{definition}
|
| 11 |
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:
|
|
| 11 |
Given $i\geq 0$, a language $L$ belongs to the class $\sigp{i}$ if there exists a polynomial time predicate $A$ and a polynomial $q$ such that:
|
|
| 12 | 12 |
$$ 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$$
|
| 13 | 13 |
where $Q_i=\forall$ (resp. $Q_i=\exists$) if $i$ is even (resp. odd). |
| 14 | 14 |
|
| ... | ... | |
| 162 | 162 |
\end{itemize}
|
| 163 | 163 |
\end{definition}
|
| 164 | 164 |
One then obtains: |
| 165 |
\begin{theorem}[\cite{BellantoniThesis}]
|
|
| 165 |
\begin{theorem}[\cite{BellantoniThesis, Bellantoni95}]
|
|
| 166 | 166 |
The class of functions representable by $\mubc$ programs is $\fph$, and for each $i$ the class representable by $\mubc^i$ programs is $\fphi{i}$.
|
| 167 | 167 |
\end{theorem}
|
| 168 | 168 |
We will also need an intermediary lemma, also proved in \cite{BellantoniThesis}.
|
Formats disponibles : Unified diff