On hard instances
Identifieur interne : 001F25 ( Main/Exploration ); précédent : 001F24; suivant : 001F26On hard instances
Auteurs : Martin Mundhenk [Allemagne]Source :
- Theoretical Computer Science [ 0304-3975 ] ; 2000.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
Instance complexity was introduced by Orponen, Ko, Schöning, and Watanabe (1994) as a measure of the complexity of individual instances of a decision problem. Comparing instance complexity to Kolmogorov complexity, they introduced the notion of p-hard instances, and conjectured that every set not in P has p-hard instances. Whereas this conjecture is still unsettled, Fortnow and Kummer [6] proved that NP-hard sets have p-hard instances, unless P=NP. The unbounded version of the conjecture was proven wrong by Kummer (1995). We introduce a slightly weaker notion of hard instances. In the unbounded version, we characterize the classes of recursive enumerable resp. recursive sets by hard instances. In bounded versions, we characterize the class P. Hard instances are shown to be stronger than complexity cores (introduced by Lynch (1975) Nevertheless, NP-hard sets must have super-polynomially dense hard instances, unless P=NP.
Url:
DOI: 10.1016/S0304-3975(98)00262-X
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001329
- to stream Istex, to step Curation: 001217
- to stream Istex, to step Checkpoint: 000C62
- to stream Main, to step Merge: 002238
- to stream PascalFrancis, to step Corpus: 000F25
- to stream PascalFrancis, to step Curation: 000044
- to stream PascalFrancis, to step Checkpoint: 000C74
- to stream Main, to step Merge: 002320
- to stream Main, to step Curation: 001F25
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>On hard instances</title><author><name sortKey="Mundhenk, Martin" sort="Mundhenk, Martin" uniqKey="Mundhenk M" first="Martin" last="Mundhenk">Martin Mundhenk</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:6CAAA4EC2F49A82366994376205EE466286ADAB9</idno><date when="2000" year="2000">2000</date><idno type="doi">10.1016/S0304-3975(98)00262-X</idno><idno type="url">https://api.istex.fr/document/6CAAA4EC2F49A82366994376205EE466286ADAB9/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001329</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001329</idno><idno type="wicri:Area/Istex/Curation">001217</idno><idno type="wicri:Area/Istex/Checkpoint">000C62</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000C62</idno><idno type="wicri:doubleKey">0304-3975:2000:Mundhenk M:on:hard:instances</idno><idno type="wicri:Area/Main/Merge">002238</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:00-0375163</idno><idno type="wicri:Area/PascalFrancis/Corpus">000F25</idno><idno type="wicri:Area/PascalFrancis/Curation">000044</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000C74</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000C74</idno><idno type="wicri:doubleKey">0304-3975:2000:Mundhenk M:on:hard:instances</idno><idno type="wicri:Area/Main/Merge">002320</idno><idno type="wicri:Area/Main/Curation">001F25</idno><idno type="wicri:Area/Main/Exploration">001F25</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">On hard instances</title><author><name sortKey="Mundhenk, Martin" sort="Mundhenk, Martin" uniqKey="Mundhenk M" first="Martin" last="Mundhenk">Martin Mundhenk</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Universität Trier, FB IV – Informatik, D-54286 Trier</wicri:regionArea><wicri:noRegion>54286 Trier</wicri:noRegion><wicri:noRegion>D-54286 Trier</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="j">Theoretical Computer Science</title><title level="j" type="abbrev">TCS</title><idno type="ISSN">0304-3975</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="2000">2000</date><biblScope unit="volume">242</biblScope><biblScope unit="issue">1–2</biblScope><biblScope unit="page" from="301">301</biblScope><biblScope unit="page" to="311">311</biblScope></imprint><idno type="ISSN">0304-3975</idno></series><idno type="istex">6CAAA4EC2F49A82366994376205EE466286ADAB9</idno><idno type="DOI">10.1016/S0304-3975(98)00262-X</idno><idno type="PII">S0304-3975(98)00262-X</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0304-3975</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm complexity</term><term>Complexity measure</term><term>Computational complexity</term><term>NP hard problem</term><term>Recursive set</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Complexité algorithme</term><term>Complexité calcul</term><term>Ensemble récursif</term><term>Mesure complexité</term><term>Problème NP difficile</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Instance complexity was introduced by Orponen, Ko, Schöning, and Watanabe (1994) as a measure of the complexity of individual instances of a decision problem. Comparing instance complexity to Kolmogorov complexity, they introduced the notion of p-hard instances, and conjectured that every set not in P has p-hard instances. Whereas this conjecture is still unsettled, Fortnow and Kummer [6] proved that NP-hard sets have p-hard instances, unless P=NP. The unbounded version of the conjecture was proven wrong by Kummer (1995). We introduce a slightly weaker notion of hard instances. In the unbounded version, we characterize the classes of recursive enumerable resp. recursive sets by hard instances. In bounded versions, we characterize the class P. Hard instances are shown to be stronger than complexity cores (introduced by Lynch (1975) Nevertheless, NP-hard sets must have super-polynomially dense hard instances, unless P=NP.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country></list><tree><country name="Allemagne"><noRegion><name sortKey="Mundhenk, Martin" sort="Mundhenk, Martin" uniqKey="Mundhenk M" first="Martin" last="Mundhenk">Martin Mundhenk</name></noRegion><name sortKey="Mundhenk, Martin" sort="Mundhenk, Martin" uniqKey="Mundhenk M" first="Martin" last="Mundhenk">Martin Mundhenk</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001F25 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001F25 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:6CAAA4EC2F49A82366994376205EE466286ADAB9
|texte= On hard instances
}}
| This area was generated with Dilib version V0.6.31. |  |