Počítače a neodolatelnost - Computers and Intractability - Wikipedia

Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti
Garey, Johnson, Intractability, cover.jpg
AutorMichael R. Garey a David S. Johnson
ZeměSpojené státy
JazykAngličtina
SérieŘada knih v matematických vědách
PředmětPočítačová věda
ŽánrUčebnice
VydavatelW. H. Freeman and Company
Datum publikace
1979
Typ médiaTisk
Stránkyx + 338
ISBN0-7167-1045-5
OCLC247570676
519.4
LC ClassQA76.6 .G35

v počítačová věda, konkrétněji teorie výpočetní složitosti, Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti je vlivná učebnice od Michael Garey a David S. Johnson.[1]Byla to první kniha výhradně o teorii NP-úplnost a výpočetní neřešitelnost.[2] Kniha obsahuje dodatek, který poskytuje důkladný souhrn NP-úplných problémů (který byl aktualizován v pozdějších výtiscích knihy). Kniha je nyní v některých ohledech zastaralá, protože nepokrývá novější vývoj, jako je Věta o PCP. Je stále v tisku a je považována za klasiku: ve studii z roku 2006 CiteSeer vyhledávač uvedl knihu jako nejcitovanější odkaz v literatuře o informatice.[3]

Otevřené problémy

Další příloha knihy představovala problémy, u nichž nebylo známo, zda jsou NP-úplné nebo v P (nebo ani jedno). Problémy (s jejich původními názvy) jsou:

  1. Graf izomorfismus
    O tomto problému je známo, že je v NP, ale není známo, zda je NP-úplný.
  2. Podgraf homeomorfismus (pro pevný graf H)
  3. Rod rodu
  4. Dokončení akordového grafu
  5. Chromatický index[4]
  6. Problém parity překlenujícího stromu[5]
  7. Dimenze částečné objednávky
  8. Plánování 3 procesorů omezeno prioritou
    Tento problém byl od roku 2016 stále otevřený.[6]
  9. Lineární programování
  10. Celková unimodularita[7]
  11. Složené číslo
    Je známo, že testování složení je v P, ale složitost úzce souvisí celočíselná faktorizace problém zůstává otevřený.
  12. Minimalizace délky triangulace[8]
    O problému 12 je známo, že je NP-tvrdý, ale není známo, zda je v NP.

Recepce

Brzy poté, co se objevila, získala kniha kladné recenze od renomovaných vědců v oblasti teoretické informatiky.

Ve své recenzi Kniha Ronalda V. doporučuje knihu „komukoli, kdo se chce dozvědět o předmětu NP-úplnost“, a výslovně zmiňuje „mimořádně užitečnou“ přílohu s více než 300 NP-výpočetními problémy. Na závěr dodává: „Počítačová věda potřebuje více knih, jako je tato.“[9]

Harry R. Lewis oceňuje matematické prózy autorů: „Kniha Gareyho a Johnsona je důkladnou, jasnou a praktickou expozicí NP-úplnosti. V mnoha ohledech je těžké si představit lepší zacházení s tímto tématem.“ Rovněž považuje dodatek za „jedinečný“ a „za výchozí bod při pokusech ukázat nové problémy jako NP-úplný“.[10]

Dvacet tři let poté, co se objevila kniha, Lance Fortnow, šéfredaktor časopisu vědecký časopis Transakce na výpočetní teorii, uvádí: „Považuji Gareyho a Johnsona za nejdůležitější knihu v mé kancelářské knihovně. Každý počítačový vědec by měl mít tuto knihu také na svých pultech. [...] Garey a Johnson mají nejlepší úvod do výpočetní složitosti, jakou jsem kdy měl vidět. “ [11]

Viz také

Reference

  1. ^ Garey, M. R.; Johnson, D. S. (1979). Victor Klee (vyd.). Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti. Série knih v matematických vědách. San Francisco, Kalifornie: W. H. Freeman and Co. pp.x + 338. ISBN  0-7167-1045-5. PAN  0519066.
  2. ^ Juris Hartmanis (1982). „Computers and Intractability: A Guide to the Theory of NP-Completeness, book review“. Recenze SIAM. 24 (1): 90–91. doi:10.1137/1024022. JSTOR  2029450.
  3. ^ „Nejcitovanější články v oboru Computer Science - září 2006 (CiteSeer.Continuity)“. Citováno 2007-11-03.
  4. ^ NP-kompletní: Holyer, Ian (listopad 1981). „NP-úplnost zbarvení hran“. SIAM Journal on Computing. 10 (4): 718–720. doi:10.1137/0210055.
  5. ^ V P: Lovász, L. Lovász, L .; Sós, V.T. (eds.). Algebraické metody v teorii grafů, svazek II (Kolokvium Szeged, 1978). Colloquia Mathematica Societatis János Bolyai, 25. Severní Holandsko. str. 495–517.
  6. ^ van Bevern, René; Bredereck, Robert; Bulteau, Laurent; Komusiewicz, Christian; Talmon, Nimrod; Woeginger, Gerhard J. (2016). "Problémy s rozvržením priority omezené parametrem částečné šířky objednávky". DOOR 2016: Diskrétní optimalizace a provozní výzkum. Přednášky z informatiky. 9869. Springer-Verlag. 105–120. arXiv:1605.00901. doi:10.1007/978-3-319-44914-2_9.
  7. ^ V P: Seymour, P. D. (červen 1980). „Rozklad regulárních matroidů“ (PDF). Journal of Combinatorial Theory, Series B. 28 (3): 305–359. doi:10.1016/0095-8956(80)90075-1.
  8. ^ Je NP tvrdé: Mulzer, Wolfgang; Rote, Günter (2008), „Triangulace s minimální hmotností je NP-tvrdá“, Deník ACM, 55 (2), čl. 11, arXiv:cs.CG/0601002, doi:10.1145/1346330.1346336, PAN  2417038
  9. ^ Kniha Ronald V. Recenze: Počítače a nepoddajnost: Průvodce po teorii NP-úplnosti Býk. Amer. Matematika. Soc. (N.S.), 3(2), str. 898–904, 1980
  10. ^ Harry R. Lewis, Recenze: Počítače a neřešitelnost: Průvodce po teorii NP-úplnosti, Journal of Symbolic Logic, Sv. 48(2), str. 498–500, 1983
  11. ^ Lance Fortnow, Great Books: Computers and Intractability: A Guide to the Theory of NP-Completeness od Michaela R. Gareyho a Davida S. Johnsona. Blog o výpočetní složitosti, 30. srpna 2002.