Implicit Complexity Over an Arbitrary Structure : Sequential and Parallel Polynomial Time
Identifieur interne : 005E56 ( Main/Curation ); précédent : 005E55; suivant : 005E57Implicit Complexity Over an Arbitrary Structure : Sequential and Parallel Polynomial Time
Auteurs : Olivier Bournez ; Felipe Cucker ; Paulin Jacobé De Naurois ; Jean-Yves MarionSource :
- Journal of Logic and Computation ; 2005.
English descriptors
Abstract
We provide several machine-independent characterizations of deterministic complexity classes in the model of computation proposed by L. Blum, M. Shub and S. Smale. We provide a characterization of partial recursive functions over any arbitrary structure. We show that polynomial time over an arbitrary structure can be characterized in terms of safe recursion. We show that polynomial parallel time over an arbitrary structure can be characterized in terms of safe recursion with substitutions.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: Pour aller vers cette notice dans l'étape Curation :004007
- to stream Crin, to step Curation: Pour aller vers cette notice dans l'étape Curation :004007
- to stream Crin, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :000304
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :006079
Links to Exploration step
CRIN:bournez04gLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="361">Implicit Complexity Over an Arbitrary Structure : Sequential and Parallel Polynomial Time</title>
</titleStmt>
<publicationStmt><idno type="RBID">CRIN:bournez04g</idno>
<date when="2005" year="2005">2005</date>
<idno type="wicri:Area/Crin/Corpus">004007</idno>
<idno type="wicri:Area/Crin/Curation">004007</idno>
<idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">004007</idno>
<idno type="wicri:Area/Crin/Checkpoint">000304</idno>
<idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">000304</idno>
<idno type="wicri:Area/Main/Merge">006079</idno>
<idno type="wicri:Area/Main/Curation">005E56</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Implicit Complexity Over an Arbitrary Structure : Sequential and Parallel Polynomial Time</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">Journal of Logic and Computation</title>
<imprint><date when="2005" type="published">2005</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>blum shub smale model</term>
<term>complexity</term>
<term>implicit complexity</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en" wicri:score="1113">We provide several machine-independent characterizations of deterministic complexity classes in the model of computation proposed by L. Blum, M. Shub and S. Smale. We provide a characterization of partial recursive functions over any arbitrary structure. We show that polynomial time over an arbitrary structure can be characterized in terms of safe recursion. We show that polynomial parallel time over an arbitrary structure can be characterized in terms of safe recursion with substitutions.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 005E56 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/biblio.hfd -nk 005E56 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Curation |type= RBID |clé= CRIN:bournez04g |texte= Implicit Complexity Over an Arbitrary Structure : Sequential and Parallel Polynomial Time }}
This area was generated with Dilib version V0.6.33. |