On hard instances
Identifieur interne : 001329 ( Istex/Corpus ); précédent : 001328; suivant : 001330On hard instances
Auteurs : Martin MundhenkSource :
- 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
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><affiliation><mods:affiliation>Universität Trier, FB IV – Informatik, D-54286 Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: mundhenk@ti.uni-trier.de</mods:affiliation></affiliation></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></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><mods:affiliation>Universität Trier, FB IV – Informatik, D-54286 Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: mundhenk@ti.uni-trier.de</mods:affiliation></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><istex><corpusName>elsevier</corpusName><author><json:item><name>Martin Mundhenk</name><affiliations><json:string>Universität Trier, FB IV – Informatik, D-54286 Trier, Germany</json:string><json:string>E-mail: mundhenk@ti.uni-trier.de</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>Full-length article</json:string></originalGenre><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.</abstract><qualityIndicators><score>6.477</score><pdfVersion>1.2</pdfVersion><pdfPageSize>408 x 660 pts</pdfPageSize><refBibsNative>true</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>933</abstractCharCount><pdfWordCount>4821</pdfWordCount><pdfCharCount>22425</pdfCharCount><pdfPageCount>11</pdfPageCount><abstractWordCount>138</abstractWordCount></qualityIndicators><title>On hard instances</title><pii><json:string>S0304-3975(98)00262-X</json:string></pii><refBibs><json:item><host><author></author></host></json:item><json:item><host><author></author><title>Structural complexity I/II, EATCS Monographs on Theoretical Computer Science</title></host></json:item><json:item><author><json:item><name>L. Berman</name></json:item><json:item><name>J. Hartmanis</name></json:item></author><host><volume>6</volume><pages><last>322</last><first>305</first></pages><issue>2</issue><author></author><title>SIAM J. Comput.</title></host><title>On isomorphisms and density of NP and other complete sets</title></json:item><json:item><author><json:item><name>H. Buhrman</name></json:item><json:item><name>L. Longpré</name></json:item><json:item><name>E. Spaan</name></json:item></author><host><pages><last>214</last><first>208</first></pages><author></author><title>Proc. 8th Structure in Complexity Theory Conf.</title></host><title>SPARSE reduces conjunctively to Tally</title></json:item><json:item><author><json:item><name>H. Buhrman</name></json:item><json:item><name>P. Orponen</name></json:item></author><host><pages><last>222</last><first>217</first></pages><author></author><title>Proc. 9th Structure in Complexity Theory Conf.</title></host><title>Random strings make hard instances</title></json:item><json:item><author><json:item><name>L. Fortnow</name></json:item><json:item><name>M. Kummer</name></json:item></author><host><volume>161</volume><pages><last>140</last><first>123</first></pages><author></author><title>Theoret. Comput. Sci.</title></host><title>On resource-bounded instance complexity</title></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>J. Köbler</name></json:item><json:item><name>O. Watanabe</name></json:item></author><host><volume>28</volume><pages><last>324</last><first>311</first></pages><issue>1</issue><author></author><title>SIAM J. Comput.</title></host><title>New collapse consequences on NP having small circuits</title></json:item><json:item><author><json:item><name>M. Kummer</name></json:item></author><host><pages><last>124</last><first>111</first></pages><author></author><title>Proc. 10th Structure in Complexity Theory Conf.</title></host><title>The instance complexity conjecture</title></json:item><json:item><host><author></author><title>An Introduction to Kolmogorov Complexity and its Applications</title></host></json:item><json:item><author><json:item><name>N. Lynch</name></json:item></author><host><volume>22</volume><pages><last>345</last><first>341</first></pages><author></author><title>J. ACM</title></host><title>On reducibility to complex or sparse sets</title></json:item><json:item><author><json:item><name>S. Mahaney</name></json:item></author><host><volume>25</volume><pages><last>143</last><first>130</first></pages><issue>2</issue><author></author><title>J. Comput. System Sci.</title></host><title>Sparse complete sets for NP, Solution of a conjecture of Berman and Hartmanis</title></json:item><json:item><author><json:item><name>M. Mundhenk</name></json:item></author><host><author></author><title>Proc. 25th Mathematical Foundations of Computer Science, Lecture Notes in Computer Science</title></host><serie><author></author><title>Proc. 25th Mathematical Foundations of Computer Science, Lecture Notes in Computer Science</title></serie><title>NP-hard sets have may hard instances</title></json:item><json:item><author><json:item><name>P. Orponen</name></json:item><json:item><name>K. Ko</name></json:item><json:item><name>U. Schöning</name></json:item><json:item><name>O. Watanabe</name></json:item></author><host><volume>41</volume><pages><last>121</last><first>96</first></pages><author></author><title>J. ACM</title></host><title>Instance complexity</title></json:item><json:item><author><json:item><name>P. Orponen</name></json:item><json:item><name>U. Schöning</name></json:item></author><host><author></author><title>11th Symp. on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science</title></host><serie><author></author><title>11th Symp. on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science</title></serie><title>The structure of polynomial complexity cores</title></json:item><json:item><host><author></author></host></json:item></refBibs><genre><json:string>research-article</json:string></genre><serie><volume>vol. 1295</volume><pages><last>437</last><first>428</first></pages><language><json:string>unknown</json:string></language><title>Proc. 25th Mathematical Foundations of Computer Science, Lecture Notes in Computer Science</title></serie><host><volume>242</volume><pii><json:string>S0304-3975(00)X0137-5</json:string></pii><pages><last>311</last><first>301</first></pages><issn><json:string>0304-3975</json:string></issn><issue>1–2</issue><genre><json:string>journal</json:string></genre><language><json:string>unknown</json:string></language><title>Theoretical Computer Science</title><publicationDate>2000</publicationDate></host><categories><wos><json:string>science</json:string><json:string>computer science, theory & methods</json:string></wos><scienceMetrix><json:string>applied sciences</json:string><json:string>information & communication technologies</json:string><json:string>computation theory & mathematics</json:string></scienceMetrix></categories><publicationDate>2000</publicationDate><copyrightDate>2000</copyrightDate><doi><json:string>10.1016/S0304-3975(98)00262-X</json:string></doi><id>6CAAA4EC2F49A82366994376205EE466286ADAB9</id><score>0.77893275</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/6CAAA4EC2F49A82366994376205EE466286ADAB9/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/6CAAA4EC2F49A82366994376205EE466286ADAB9/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/6CAAA4EC2F49A82366994376205EE466286ADAB9/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">On hard instances</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>©2000 Elsevier Science B.V.</p></availability><date>2000</date></publicationStmt><notesStmt><note>Communicated by O. Watanabe</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">On hard instances</title><author xml:id="author-1"><persName><forename type="first">Martin</forename><surname>Mundhenk</surname></persName><email>mundhenk@ti.uni-trier.de</email><note type="biography">A preliminary version was presented at MFCS’97 [13]. Supported in part by the Office of the Vice Chancellor for Research and Graduate Studies at the University of Kentucky, and by Deutsche Forschungsgemeinschaft (DFG), grant Mu 1226/2-1.</note><affiliation>A preliminary version was presented at MFCS’97 [13]. Supported in part by the Office of the Vice Chancellor for Research and Graduate Studies at the University of Kentucky, and by Deutsche Forschungsgemeinschaft (DFG), grant Mu 1226/2-1.</affiliation><affiliation>Universität Trier, FB IV – Informatik, D-54286 Trier, Germany</affiliation></author></analytic><monogr><title level="j">Theoretical Computer Science</title><title level="j" type="abbrev">TCS</title><idno type="pISSN">0304-3975</idno><idno type="PII">S0304-3975(00)X0137-5</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="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></monogr><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></fileDesc><profileDesc><creation><date>2000</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>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.</p></abstract></profileDesc><revisionDesc><change when="1998-03-01">Modified</change><change when="2000">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/6CAAA4EC2F49A82366994376205EE466286ADAB9/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>TCS</jid><aid>3071</aid><ce:pii>S0304-3975(98)00262-X</ce:pii><ce:doi>10.1016/S0304-3975(98)00262-X</ce:doi><ce:copyright type="full-transfer" year="2000">Elsevier Science B.V.</ce:copyright></item-info><head><ce:title>On hard instances</ce:title><ce:author-group><ce:author><ce:given-name>Martin</ce:given-name><ce:surname>Mundhenk</ce:surname><ce:cross-ref refid="FN1"><ce:sup>1</ce:sup></ce:cross-ref><ce:e-address>mundhenk@ti.uni-trier.de</ce:e-address></ce:author><ce:affiliation><ce:textfn>Universität Trier, FB IV – Informatik, D-54286 Trier, Germany</ce:textfn></ce:affiliation><ce:footnote id="FN1"><ce:label>1</ce:label><ce:note-para>A preliminary version was presented at MFCS’97 [13]. Supported in part by the Office of the Vice Chancellor for Research and Graduate Studies at the University of Kentucky, and by Deutsche Forschungsgemeinschaft (DFG), grant Mu 1226/2-1.</ce:note-para></ce:footnote></ce:author-group><ce:date-received day="1" month="9" year="1997"></ce:date-received><ce:date-revised day="1" month="3" year="1998"></ce:date-revised><ce:miscellaneous>Communicated by O. Watanabe</ce:miscellaneous><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para><ce:italic>Instance complexity</ce:italic> 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 <math altimg="si1.gif">p</math>-hard instances, and conjectured that every set not in P has <math altimg="si2.gif">p</math>-hard instances. Whereas this conjecture is still unsettled, Fortnow and Kummer [6] proved that NP-hard sets have <math altimg="si3.gif">p</math>-hard instances, unless P=NP. The unbounded version of the conjecture was proven wrong by Kummer (1995).</ce:simple-para><ce:simple-para>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.</ce:simple-para></ce:abstract-sec></ce:abstract></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>On hard instances</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>On hard instances</title></titleInfo><name type="personal"><namePart type="given">Martin</namePart><namePart type="family">Mundhenk</namePart><affiliation>Universität Trier, FB IV – Informatik, D-54286 Trier, Germany</affiliation><affiliation>E-mail: mundhenk@ti.uni-trier.de</affiliation><description>A preliminary version was presented at MFCS’97 [13]. Supported in part by the Office of the Vice Chancellor for Research and Graduate Studies at the University of Kentucky, and by Deutsche Forschungsgemeinschaft (DFG), grant Mu 1226/2-1.</description><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="Full-length article"></genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">2000</dateIssued><dateModified encoding="w3cdtf">1998-03-01</dateModified><copyrightDate encoding="w3cdtf">2000</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract 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.</abstract><note>Communicated by O. Watanabe</note><relatedItem type="host"><titleInfo><title>Theoretical Computer Science</title></titleInfo><titleInfo type="abbreviated"><title>TCS</title></titleInfo><genre type="journal">journal</genre><originInfo><dateIssued encoding="w3cdtf">20000706</dateIssued></originInfo><identifier type="ISSN">0304-3975</identifier><identifier type="PII">S0304-3975(00)X0137-5</identifier><part><date>20000706</date><detail type="volume"><number>242</number><caption>vol.</caption></detail><detail type="issue"><number>1–2</number><caption>no.</caption></detail><extent unit="issue pages"><start>1</start><end>500</end></extent><extent unit="pages"><start>301</start><end>311</end></extent></part></relatedItem><identifier type="istex">6CAAA4EC2F49A82366994376205EE466286ADAB9</identifier><identifier type="DOI">10.1016/S0304-3975(98)00262-X</identifier><identifier type="PII">S0304-3975(98)00262-X</identifier><accessCondition type="use and reproduction" contentType="copyright">©2000 Elsevier Science B.V.</accessCondition><recordInfo><recordContentSource>ELSEVIER</recordContentSource><recordOrigin>Elsevier Science B.V., ©2000</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001329 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001329 | 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= Corpus
|type= RBID
|clé= ISTEX:6CAAA4EC2F49A82366994376205EE466286ADAB9
|texte= On hard instances
}}
| This area was generated with Dilib version V0.6.31. |  |