Révision 163
| CSL17/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}.
|
| CSL17/ph-biblio.bib (revision 163) | ||
|---|---|---|
| 48 | 48 |
pages = {97--110},
|
| 49 | 49 |
year = {1992}
|
| 50 | 50 |
} |
| 51 |
|
|
| 52 |
@inproceedings{Bellantoni95,
|
|
| 53 |
author = {Stephen Bellantoni},
|
|
| 54 |
title = {Predicative Recursion and The Polytime Hierarchy},
|
|
| 55 |
booktitle = {Feasible Mathematics II},
|
|
| 56 |
pages = {15-29},
|
|
| 57 |
series = {Progress in Computer Science and Applied Logic},
|
|
| 58 |
volume = {13},
|
|
| 59 |
editors ={Clote P., Remmel J.B.},
|
|
| 60 |
publisher = {Birkhauser Boston},
|
|
| 61 |
year = {1995}
|
|
| 62 |
} |
|
| 51 | 63 |
|
| 64 |
|
|
| 52 | 65 |
@inproceedings{Cobham,
|
| 53 | 66 |
author = {Cobham, A.},
|
| 54 | 67 |
title = {On the intrinsic computational difficulty of functions},
|
Formats disponibles : Unified diff