On hard instances
Identifieur interne : 000C62 ( Istex/Checkpoint ); précédent : 000C61; suivant : 000C63On hard instances
Auteurs : Martin Mundhenk [Allemagne]Source :
- Theoretical Computer Science [ 0304-3975 ] ; 2000.
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...)
Links to Exploration step
ISTEX:6CAAA4EC2F49A82366994376205EE466286ADAB9Le 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>
</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></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/Istex/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C62 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Checkpoint/biblio.hfd -nk 000C62 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Rhénanie |area= UnivTrevesV1 |flux= Istex |étape= Checkpoint |type= RBID |clé= ISTEX:6CAAA4EC2F49A82366994376205EE466286ADAB9 |texte= On hard instances }}
![]() | This area was generated with Dilib version V0.6.31. | ![]() |