Datorer och svårhanterlighet
 | |
| Författare | Michael R. Garey och David S. Johnson |
|---|---|
| Land | Förenta staterna |
| Språk | engelsk |
| Serier | En serie böcker i de matematiska vetenskaperna |
| Ämne | Datavetenskap |
| Genre | Lärobok |
| Utgivare | W. H. Freeman and Company |
Publiceringsdatum |
1979 |
| Mediatyp | Skriva ut |
| Sidor | x+338 |
| ISBN | 0-7167-1045-5 |
| OCLC | 247570676 |
| 519,4 | |
| LC klass | QA76.6 .G35 |
Computers and Intractability: A Guide to the Theory of NP-Completeness är en lärobok av Michael Garey och David S. Johnson . Det var den första boken uteslutande om teorin om NP-fullständighet och beräkningsmöjlighet . Boken innehåller en bilaga som ger ett grundligt kompendium av NP-kompletta problem (som uppdaterades i senare tryckningar av boken). Boken är nu föråldrad i vissa avseenden eftersom den inte täcker nyare utveckling som PCP-satsen . Den finns trots allt fortfarande i tryck och betraktas som en klassiker: i en studie från 2006 CiteSeer boken som den mest citerade referensen inom datavetenskaplig litteratur.
Öppna problem
En annan bilaga till boken innehöll problem för vilka det inte var känt om de var NP-kompletta eller i P (eller ingetdera). Problemen (med deras ursprungliga namn) är:
-
Grafisomorfism
- Detta problem är känt för att finnas i NP, men det är okänt om det är NP-komplett.
- Subgraf homeomorfism (för en fast graf H )
- Graf släkte
- Färdigställande av ackordsdiagram
- Kromatiskt index
- Spännande trädparitetsproblem
- Delorderdimension
- Precedens begränsad schemaläggning med 3 processorer
- Det här problemet var fortfarande öppet från och med 2016.
- Linjär programmering
- Total unimodularitet
-
Sammansatt antal
- Testning av sammansatthet är känt för att vara i P, men komplexiteten i det närbesläktade heltalsfaktoriseringsproblemet förblir öppet.
-
Minsta längd triangulering
- Problem 12 är känt för att vara NP-hårt, men det är okänt om det är i NP.
Reception
Strax efter att den dök upp fick boken positiva recensioner av välrenommerade forskare inom området teoretisk datavetenskap.
I sin recension rekommenderar Ronald V. Book boken till "alla som vill lära sig om ämnet NP-fullständighet", och han nämner uttryckligen den "extremt användbara" bilagan med över 300 NP-hårda beräkningsproblem. Han avslutar: "Datavetenskap behöver fler böcker som den här."
Harry R. Lewis berömmer författarnas matematiska prosa: "Garey och Johnsons bok är en grundlig, tydlig och praktisk beskrivning av NP-fullständighet. I många avseenden är det svårt att föreställa sig en bättre behandling av ämnet." Han anser också att bilagan är "unik" och "som en utgångspunkt i försök att visa att nya problem är NP-kompletta".
Tjugotre år efter att boken kom ut säger Lance Fortnow , chefredaktör för den vetenskapliga tidskriften Transactions on Computational Theory : "Jag anser att Garey och Johnson är den enskilt viktigaste boken på min kontorsbokhylla. Varje datavetare borde ha detta bok på sina hyllor också. [...] Garey och Johnson har den bästa introduktionen till beräkningskomplexitet jag någonsin sett."