Implicit Complexity over an Arbitrary Structure : Quantifier Alternations
Identifieur interne : 006143 ( Main/Merge ); précédent : 006142; suivant : 006144Implicit Complexity over an Arbitrary Structure : Quantifier Alternations
Auteurs : Olivier Bournez ; Felipe Cucker ; Paulin Jacobé De Naurois ; Jean-Yves MarionSource :
- Information and Computation ; 2005.
Abstract
We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L. Blum, M. Shub and S. Smale. We show that the levels of the polynomial hier- archy correspond to safe recursion with predicative minimization and the levels of the digital polynomial hierarchy to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 004277
- to stream Crin, to step Curation: 004277
- to stream Crin, to step Checkpoint: 000368
Links to Exploration step
CRIN:bournez05fLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="300">Implicit Complexity over an Arbitrary Structure : Quantifier Alternations</title></titleStmt><publicationStmt><idno type="RBID">CRIN:bournez05f</idno><date when="2005" year="2005">2005</date><idno type="wicri:Area/Crin/Corpus">004277</idno><idno type="wicri:Area/Crin/Curation">004277</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">004277</idno><idno type="wicri:Area/Crin/Checkpoint">000368</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">000368</idno><idno type="wicri:Area/Main/Merge">006143</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Implicit Complexity over an Arbitrary Structure : Quantifier Alternations</title><author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name></author><author><name sortKey="Cucker, Felipe" sort="Cucker, Felipe" uniqKey="Cucker F" first="Felipe" last="Cucker">Felipe Cucker</name></author><author><name sortKey="Jacobe De Naurois, Paulin" sort="Jacobe De Naurois, Paulin" uniqKey="Jacobe De Naurois P" first="Paulin" last="Jacobé De Naurois">Paulin Jacobé De Naurois</name></author><author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name></author></analytic><series><title level="j">Information and Computation</title><imprint><date when="2005" type="published">2005</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="2455">We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L. Blum, M. Shub and S. Smale. We show that the levels of the polynomial hier- archy correspond to safe recursion with predicative minimization and the levels of the digital polynomial hierarchy to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006143 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 006143 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= CRIN:bournez05f
|texte= Implicit Complexity over an Arbitrary Structure : Quantifier Alternations
}}
| This area was generated with Dilib version V0.6.33. |  |