Minimization and NP multifunctions
Identifieur interne :
000379 ( PascalFrancis/Curation );
précédent :
000378;
suivant :
000380
Minimization and NP multifunctions
Auteurs : N. Danner [
États-Unis] ;
C. Pollett [
États-Unis]
Source :
-
Theoretical computer science [ 0304-3975 ] ; 2004.
RBID : Pascal:04-0318318
Descripteurs français
English descriptors
Abstract
The implicit characterizations of the polynomial-time computable functions FP given by Bellantoni-Cook and Leivant suggest that this class is the complexity-theoretic analog of the primitive recursive functions. Hence, it is natural to add minimization operators to these characterizations and investigate the resulting class of partial functions as a candidate for the analog of the partial recursive functions. We do so in this paper for Cobham's definition of FP by bounded recursion and for Bellantoni-Cook's safe recursion and prove that the resulting classes capture exactly NPMV, the nondeterministic polynomial-time computable partial multifunctions. We also consider the relationship between our schemes and a notion of nondeterministic recursion defined by Leivant and show that the latter characterizes the total functions of NPMV. We view these results as giving evidence that NPMV is the appropriate analog of partial recursive. This view is reinforced by earlier results of Spreen and Stahl who show that for many of the relationships between partial recursive functions and r.e. sets, analogous relationships hold between NPMV and NP sets. Furthermore, since NPMV is obtained from FP in the same way as the recursive functions are obtained from the primitive recursive functions (when defined via function schemes), this also gives further evidence that FP is properly seen as playing the role of primitive recursion.
| pA |
| A01 | 01 | 1 | | @0 0304-3975 |
|---|
| A02 | 01 | | | @0 TCSCDI |
|---|
| A03 | | 1 | | @0 Theor. comput. sci. |
|---|
| A05 | | | | @2 318 |
|---|
| A06 | | | | @2 1-2 |
|---|
| A08 | 01 | 1 | ENG | @1 Minimization and NP multifunctions |
|---|
| A09 | 01 | 1 | ENG | @1 Implicit computational complexity |
|---|
| A11 | 01 | 1 | | @1 DANNER (N.) |
|---|
| A11 | 02 | 1 | | @1 POLLETT (C.) |
|---|
| A12 | 01 | 1 | | @1 MARION (Jean-Yves) @9 ed. |
|---|
| A14 | 01 | | | @1 Department of Mathematics, University of California Los Angeles @2 Los Angeles, CA 90095-1555 @3 USA @Z 1 aut. |
|---|
| A14 | 02 | | | @1 Department of Mathematics and Computer Science, San Jose State University @2 San Jose, CA 95192 @3 USA @Z 2 aut. |
|---|
| A15 | 01 | | | @1 LORIA-INPL, Ecole Nationale Superieure des Mines de Nancy, BP 239 @2 Vandoeuvre-les-Nancy 54506 @3 FRA @Z 1 aut. |
|---|
| A20 | | | | @1 105-119 |
|---|
| A21 | | | | @1 2004 |
|---|
| A23 | 01 | | | @0 ENG |
|---|
| A43 | 01 | | | @1 INIST @2 17243 @5 354000110408220050 |
|---|
| A44 | | | | @0 0000 @1 © 2004 INIST-CNRS. All rights reserved. |
|---|
| A45 | | | | @0 8 ref. |
|---|
| A47 | 01 | 1 | | @0 04-0318318 |
|---|
| A60 | | | | @1 P @2 C |
|---|
| A61 | | | | @0 A |
|---|
| A64 | 01 | 1 | | @0 Theoretical computer science |
|---|
| A66 | 01 | | | @0 NLD |
|---|
| C01 | 01 | | ENG | @0 The implicit characterizations of the polynomial-time computable functions FP given by Bellantoni-Cook and Leivant suggest that this class is the complexity-theoretic analog of the primitive recursive functions. Hence, it is natural to add minimization operators to these characterizations and investigate the resulting class of partial functions as a candidate for the analog of the partial recursive functions. We do so in this paper for Cobham's definition of FP by bounded recursion and for Bellantoni-Cook's safe recursion and prove that the resulting classes capture exactly NPMV, the nondeterministic polynomial-time computable partial multifunctions. We also consider the relationship between our schemes and a notion of nondeterministic recursion defined by Leivant and show that the latter characterizes the total functions of NPMV. We view these results as giving evidence that NPMV is the appropriate analog of partial recursive. This view is reinforced by earlier results of Spreen and Stahl who show that for many of the relationships between partial recursive functions and r.e. sets, analogous relationships hold between NPMV and NP sets. Furthermore, since NPMV is obtained from FP in the same way as the recursive functions are obtained from the primitive recursive functions (when defined via function schemes), this also gives further evidence that FP is properly seen as playing the role of primitive recursion. |
|---|
| C02 | 01 | X | | @0 001D02A05 |
|---|
| C02 | 02 | X | | @0 001A02A01D |
|---|
| C03 | 01 | X | FRE | @0 Minimisation @5 17 |
|---|
| C03 | 01 | X | ENG | @0 Minimization @5 17 |
|---|
| C03 | 01 | X | SPA | @0 Minimización @5 17 |
|---|
| C03 | 02 | X | FRE | @0 Temps polynomial @5 21 |
|---|
| C03 | 02 | X | ENG | @0 Polynomial time @5 21 |
|---|
| C03 | 02 | X | SPA | @0 Tiempo polinomial @5 21 |
|---|
| C03 | 03 | X | FRE | @0 Classe complexité @5 22 |
|---|
| C03 | 03 | X | ENG | @0 Complexity class @5 22 |
|---|
| C03 | 03 | X | SPA | @0 Clase complejidad @5 22 |
|---|
| C03 | 04 | X | FRE | @0 Fonction récursive @5 25 |
|---|
| C03 | 04 | X | ENG | @0 Recursive function @5 25 |
|---|
| C03 | 04 | X | SPA | @0 Función recursiva @5 25 |
|---|
| C03 | 05 | X | FRE | @0 Informatique théorique @5 27 |
|---|
| C03 | 05 | X | ENG | @0 Computer theory @5 27 |
|---|
| C03 | 05 | X | SPA | @0 Informática teórica @5 27 |
|---|
| C03 | 06 | X | FRE | @0 Fonction FP @4 CD @5 96 |
|---|
| C03 | 06 | X | ENG | @0 FP function @4 CD @5 96 |
|---|
| C03 | 07 | X | FRE | @0 Multification @4 CD @5 97 |
|---|
| C03 | 07 | X | ENG | @0 Multification @4 CD @5 97 |
|---|
| N21 | | | | @1 187 |
|---|
| N44 | 01 | | | @1 OTO |
|---|
| N82 | | | | @1 OTO |
|---|
|
|---|
| pR |
| A30 | 01 | 1 | ENG | @1 ICC Workshop @3 Santa Barbara, CA USA @4 2000 |
|---|
|
|---|
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000662
Links to Exploration step
Pascal:04-0318318
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Minimization and NP multifunctions</title>
<author><name sortKey="Danner, N" sort="Danner, N" uniqKey="Danner N" first="N." last="Danner">N. Danner</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Department of Mathematics, University of California Los Angeles</s1>
<s2>Los Angeles, CA 90095-1555</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><country>États-Unis</country>
</affiliation><author><name sortKey="Pollett, C" sort="Pollett, C" uniqKey="Pollett C" first="C." last="Pollett">C. Pollett</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Department of Mathematics and Computer Science, San Jose State University</s1>
<s2>San Jose, CA 95192</s2>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14><country>États-Unis</country>
</affiliation><publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">04-0318318</idno>
<date when="2004">2004</date>
<idno type="stanalyst">PASCAL 04-0318318 INIST</idno>
<idno type="RBID">Pascal:04-0318318</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000662</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000379</idno>
</publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Minimization and NP multifunctions</title>
<author><name sortKey="Danner, N" sort="Danner, N" uniqKey="Danner N" first="N." last="Danner">N. Danner</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Department of Mathematics, University of California Los Angeles</s1>
<s2>Los Angeles, CA 90095-1555</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><country>États-Unis</country>
</affiliation><author><name sortKey="Pollett, C" sort="Pollett, C" uniqKey="Pollett C" first="C." last="Pollett">C. Pollett</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Department of Mathematics and Computer Science, San Jose State University</s1>
<s2>San Jose, CA 95192</s2>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14><country>États-Unis</country>
</affiliation><series><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
<imprint><date when="2004">2004</date>
</imprint><seriesStmt><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
</seriesStmt><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Complexity class</term>
<term>Computer theory</term>
<term>FP function</term>
<term>Minimization</term>
<term>Multification</term>
<term>Polynomial time</term>
<term>Recursive function</term>
</keywords><keywords scheme="Pascal" xml:lang="fr"><term>Minimisation</term>
<term>Temps polynomial</term>
<term>Classe complexité</term>
<term>Fonction récursive</term>
<term>Informatique théorique</term>
<term>Fonction FP</term>
<term>Multification</term>
</keywords><front><div type="abstract" xml:lang="en">The implicit characterizations of the polynomial-time computable functions FP given by Bellantoni-Cook and Leivant suggest that this class is the complexity-theoretic analog of the primitive recursive functions. Hence, it is natural to add minimization operators to these characterizations and investigate the resulting class of partial functions as a candidate for the analog of the partial recursive functions. We do so in this paper for Cobham's definition of FP by bounded recursion and for Bellantoni-Cook's safe recursion and prove that the resulting classes capture exactly NPMV, the nondeterministic polynomial-time computable partial multifunctions. We also consider the relationship between our schemes and a notion of nondeterministic recursion defined by Leivant and show that the latter characterizes the total functions of NPMV. We view these results as giving evidence that NPMV is the appropriate analog of partial recursive. This view is reinforced by earlier results of Spreen and Stahl who show that for many of the relationships between partial recursive functions and r.e. sets, analogous relationships hold between NPMV and NP sets. Furthermore, since NPMV is obtained from FP in the same way as the recursive functions are obtained from the primitive recursive functions (when defined via function schemes), this also gives further evidence that FP is properly seen as playing the role of primitive recursion.</div>
</front><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0304-3975</s0>
</fA01><fA02 i1="01"><s0>TCSCDI</s0>
</fA02><fA03 i2="1"><s0>Theor. comput. sci.</s0>
</fA03><fA05><s2>318</s2>
</fA05><fA06><s2>1-2</s2>
</fA06><fA08 i1="01" i2="1" l="ENG"><s1>Minimization and NP multifunctions</s1>
</fA08><fA09 i1="01" i2="1" l="ENG"><s1>Implicit computational complexity</s1>
</fA09><fA11 i1="01" i2="1"><s1>DANNER (N.)</s1>
</fA11><fA11 i1="02" i2="1"><s1>POLLETT (C.)</s1>
</fA11><fA12 i1="01" i2="1"><s1>MARION (Jean-Yves)</s1>
<s9>ed.</s9>
</fA12><fA14 i1="01"><s1>Department of Mathematics, University of California Los Angeles</s1>
<s2>Los Angeles, CA 90095-1555</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</fA14><fA14 i1="02"><s1>Department of Mathematics and Computer Science, San Jose State University</s1>
<s2>San Jose, CA 95192</s2>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</fA14><fA15 i1="01"><s1>LORIA-INPL, Ecole Nationale Superieure des Mines de Nancy, BP 239</s1>
<s2>Vandoeuvre-les-Nancy 54506</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA15><fA20><s1>105-119</s1>
</fA20><fA21><s1>2004</s1>
</fA21><fA23 i1="01"><s0>ENG</s0>
</fA23><fA43 i1="01"><s1>INIST</s1>
<s2>17243</s2>
<s5>354000110408220050</s5>
</fA43><fA44><s0>0000</s0>
<s1>© 2004 INIST-CNRS. All rights reserved.</s1>
</fA44><fA45><s0>8 ref.</s0>
</fA45><fA47 i1="01" i2="1"><s0>04-0318318</s0>
</fA47><fA60><s1>P</s1>
<s2>C</s2>
</fA60><fA64 i1="01" i2="1"><s0>Theoretical computer science</s0>
</fA64><fA66 i1="01"><s0>NLD</s0>
</fA66><fC01 i1="01" l="ENG"><s0>The implicit characterizations of the polynomial-time computable functions FP given by Bellantoni-Cook and Leivant suggest that this class is the complexity-theoretic analog of the primitive recursive functions. Hence, it is natural to add minimization operators to these characterizations and investigate the resulting class of partial functions as a candidate for the analog of the partial recursive functions. We do so in this paper for Cobham's definition of FP by bounded recursion and for Bellantoni-Cook's safe recursion and prove that the resulting classes capture exactly NPMV, the nondeterministic polynomial-time computable partial multifunctions. We also consider the relationship between our schemes and a notion of nondeterministic recursion defined by Leivant and show that the latter characterizes the total functions of NPMV. We view these results as giving evidence that NPMV is the appropriate analog of partial recursive. This view is reinforced by earlier results of Spreen and Stahl who show that for many of the relationships between partial recursive functions and r.e. sets, analogous relationships hold between NPMV and NP sets. Furthermore, since NPMV is obtained from FP in the same way as the recursive functions are obtained from the primitive recursive functions (when defined via function schemes), this also gives further evidence that FP is properly seen as playing the role of primitive recursion.</s0>
</fC01><fC02 i1="01" i2="X"><s0>001D02A05</s0>
</fC02><fC02 i1="02" i2="X"><s0>001A02A01D</s0>
</fC02><fC03 i1="01" i2="X" l="FRE"><s0>Minimisation</s0>
<s5>17</s5>
</fC03><fC03 i1="01" i2="X" l="ENG"><s0>Minimization</s0>
<s5>17</s5>
</fC03><fC03 i1="01" i2="X" l="SPA"><s0>Minimización</s0>
<s5>17</s5>
</fC03><fC03 i1="02" i2="X" l="FRE"><s0>Temps polynomial</s0>
<s5>21</s5>
</fC03><fC03 i1="02" i2="X" l="ENG"><s0>Polynomial time</s0>
<s5>21</s5>
</fC03><fC03 i1="02" i2="X" l="SPA"><s0>Tiempo polinomial</s0>
<s5>21</s5>
</fC03><fC03 i1="03" i2="X" l="FRE"><s0>Classe complexité</s0>
<s5>22</s5>
</fC03><fC03 i1="03" i2="X" l="ENG"><s0>Complexity class</s0>
<s5>22</s5>
</fC03><fC03 i1="03" i2="X" l="SPA"><s0>Clase complejidad</s0>
<s5>22</s5>
</fC03><fC03 i1="04" i2="X" l="FRE"><s0>Fonction récursive</s0>
<s5>25</s5>
</fC03><fC03 i1="04" i2="X" l="ENG"><s0>Recursive function</s0>
<s5>25</s5>
</fC03><fC03 i1="04" i2="X" l="SPA"><s0>Función recursiva</s0>
<s5>25</s5>
</fC03><fC03 i1="05" i2="X" l="FRE"><s0>Informatique théorique</s0>
<s5>27</s5>
</fC03><fC03 i1="05" i2="X" l="ENG"><s0>Computer theory</s0>
<s5>27</s5>
</fC03><fC03 i1="05" i2="X" l="SPA"><s0>Informática teórica</s0>
<s5>27</s5>
</fC03><fC03 i1="06" i2="X" l="FRE"><s0>Fonction FP</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03><fC03 i1="06" i2="X" l="ENG"><s0>FP function</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03><fC03 i1="07" i2="X" l="FRE"><s0>Multification</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03><fC03 i1="07" i2="X" l="ENG"><s0>Multification</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03><fN21><s1>187</s1>
</fN21><fN44 i1="01"><s1>OTO</s1>
</fN44><fN82><s1>OTO</s1>
</fN82><pR><fA30 i1="01" i2="1" l="ENG"><s1>ICC Workshop</s1>
<s3>Santa Barbara, CA USA</s3>
<s4>2000</s4>
</fA30>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000379 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Curation/biblio.hfd -nk 000379 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Curation
|type= RBID
|clé= Pascal:04-0318318
|texte= Minimization and NP multifunctions
}}
| This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022 |  |
