(NP complete) – NP‑fullständiga problem eller NP‑kompletta problem – en klass av matematiska problem som är tidskrävande att lösa och också tidskrävande att verifiera (att bevisa att lösningen är rätt). – NP‑fullständiga problem är den mest ohanterliga typen av matematiska problem. Det mest kända exemplet är handelsresandeproblemet. – Typiskt för NP‑fullständiga problem är:
- – att det inte finns något sätt – ingen algoritm – att hitta den bästa lösningen, förutom en uttömmande sökning;
- – att det inte går att bevisa att man har funnit den bästa lösningen, utom genom att jämföra alla tänkbara lösningar.
– Andra, enklare klasser av matematiska problem är P och NP. – Se också komplexitet. – Välkända NP‑fullständiga problem gäller att hitta den kortaste vägen (handelsresandeproblemet, Hamiltons problem) eller att utnyttja ett utrymme så effektivt som möjligt (kappsäcksproblemet). Metoder för att lösa NP‑fullständiga problem har praktisk tillämpning, till exempel vid kretskonstruktion, transporter och kommunikation. I praktisk tillämpning räcker det ofta med att hitta en tillräckligt bra lösning, inte nödvändigtvis den bevisat bästa. – Utom i enkla fall är det mycket tidskrävande att lösa NP‑fullständiga program. Problem av denna typ blir snabbt ohanterliga, till exempel om man ökar antalet städer i handelsresandeproblemet till några tiotal. Det är lätt att formulera NP‑fullständiga problem som det skulle ta tusentals år att lösa med dagens snabbaste datorer. – NP‑fullständiga tal är en speciell typ av tal i NP‑klassen. Ingen har hittills funnit ett sätt att lösa NP‑fullständiga problem förutom genom en uttömmande prövning av alla tänkbara lösningar. Å andra sidan har ingen heller kunnat bevisa att en sådan algoritm inte kan finnas. (Se P=NP?.) – Matematiker diskuterar ifall de NP‑fullständiga problemen är en sort för sig, eller bara en typ av NP‑problem som vi ännu inte har kommit på hur man löser. Däremot har det bevisats att om någon hittar en algoritm som löser ett NP‑fullständigt problem så kan man med samma algoritm lösa alla andra NP‑fullständiga problem.
[matematik och logik] [ändrad 2 maj 2017]