NP-hårdhed - NP-hardness
I beregningskompleksitetsteori er NP-hårdhed ( ikke-deterministisk polynom-tid- hårdhed) den definerende egenskab for en klasse af problemer, der er uformelt "mindst lige så hårde som de sværeste problemer i NP ". Et simpelt eksempel på et NP-hårdt problem er delmængdeproblemet .
En mere præcis specifikation er: et problem H er NP-hårdt, når hvert problem L i NP kan reduceres i polynomisk tid til H ; det vil sige, forudsat at en opløsning til H tager 1 enhed tid, kan H 's løsning bruges til at løse L i polynomisk tid. Som en konsekvens vil det at finde en polynomial tidsalgoritme til at løse ethvert NP-hårdt problem give polynomial tidsalgoritmer for alle problemerne i NP. Da det mistænkes for at P NP , er det usandsynligt, at der findes en sådan algoritme.
En almindelig misforståelse er, at NP i "NP-hårdt" står for "ikke-polynom", når det faktisk står for " ikke-deterministiske polynom acceptable problemer". Det mistænkes, at der ikke er nogen polynomialtidsalgoritmer for NP-hårde problemer, men det er ikke bevist. Desuden er klassen P , hvor alle problemer kan løses i polynomisk tid, indeholdt i NP- klassen.
Definition
En beslutning problem H er NP-hårdt, når for ethvert problem L i NP, er der en polynomiel tid mange-én reduktion fra L til H . En tilsvarende definition er at kræve, at alle problemer L i NP kan løses i polynomiel tid af en orakel maskine med et orakel for H . Uformelt kan man tænke på en algoritme, der kalder en sådan orakelmaskine som en subrutine til løsning af H og løser L på polynomisk tid, hvis subrutinekaldet kun tager et trin at beregne.
En anden definition er at kræve, at der være et polynomium-tid reduktion fra et NP-komplet problem G til H . Da ethvert problem L i NP reducerer i polynomisk tid til G , reduceres L igen til H i polynomial tid, så denne nye definition indebærer den foregående. Og slog sig, betyder det ikke begrænser klassen NP-hårdt at beslutningsproblemer, og det omfatter også søge problemer eller optimeringsproblemer .
Konsekvenser
Hvis P ≠ NP, kunne NP-hårde problemer ikke løses på polynomisk tid.
Nogle NP-hårde optimeringsproblemer kan tilnærmes polynomisk tid op til noget konstant tilnærmelsesforhold (især dem i APX ) eller endda op til et hvilket som helst tilnærmelsesforhold (dem i PTAS eller FPTAS ).
Eksempler
Et eksempel på et NP-hårdt problem er beslutningen delmængde sum problem : givet et sæt af heltal, tilføjer nogen ikke-tom delmængde af dem op til nul? Det er et beslutningsproblem og tilfældigvis NP-komplet. Et andet eksempel på et NP-hårdt problem er optimeringsproblemet med at finde den billigste cykliske rute gennem alle noder i en vægtet graf. Dette er almindeligt kendt som det rejsende sælgerproblem .
Der er beslutningsproblemer, der er NP-hårde, men ikke NP-komplette, såsom det stoppende problem . Det er problemet, der spørger "får et program og dets input, vil det køre for evigt?" Det er et ja / nej- spørgsmål, og det samme er et beslutningsproblem. Det er let at bevise, at stopproblemet er NP-hårdt, men ikke NP-komplet. For eksempel kan det boolske tilfredshedsproblem reduceres til det stoppende problem ved at omdanne det til beskrivelsen af en Turing-maskine, der prøver alle sandhedsværditildelinger, og når den finder en, der opfylder formlen, stopper den, og ellers går den i en uendelig løkke. Det er også let at se, at standsningsproblemet ikke er i NP, da alle problemer i NP kan afgøres i et begrænset antal operationer, men standsningsproblemet generelt er uafgøreligt . Der er også NP-hårde problemer, der hverken er NP-komplette eller ubeslutsomme . For eksempel kan sproget i ægte kvantificerede boolske formler bestemmes i polynomrum , men ikke i ikke-deterministisk polynomtid (medmindre NP = PSPACE ).
NP-navngivningskonvention
NP-hårde problemer behøver ikke at være elementer i kompleksitetsklassen NP. Da NP spiller en central rolle i beregningskompleksitet , bruges det som basis for flere klasser:
- NP
- Klasse af beregningsmæssige beslutningsproblemer, for hvilke en given ja- løsning kan verificeres som en løsning i polynomisk tid af en deterministisk Turing-maskine (eller kan løses af en ikke-deterministisk Turing-maskine i polynomisk tid).
- NP-hård
- Klasse af problemer, der er mindst lige så hårde som de sværeste problemer i NP. Problemer, der er NP-hårde, behøver ikke at være elementer i NP; faktisk kan de ikke engang være besluttelige.
- NP-komplet
- Klasse af beslutningsproblemer, der indeholder de sværeste problemer i NP. Hvert NP-komplet problem skal være i NP.
- NP-let
- Højst så hårdt som NP, men ikke nødvendigvis i NP.
- NP-ækvivalent
- Beslutningsproblemer, der både er NP-hårde og NP-lette, men ikke nødvendigvis i NP.
- NP-mellemliggende
- Hvis P og NP er forskellige, så findes der beslutningsproblemer i regionen NP, der falder mellem P og NP-komplette problemer. (Hvis P og NP er den samme klasse, eksisterer der ikke NP-mellemliggende problemer, fordi i dette tilfælde hvert NP-komplet problem falder i P, og pr. Definition kan ethvert problem i NP reduceres til et NP-komplet problem. )
Anvendelsesområder
NP-hårde problemer tackles ofte med reglerbaserede sprog i områder, herunder:
- Omtrentlige computing
- Konfiguration
- Kryptografi
- Data minedrift
- Beslutningsstøtte
- Fylogenetik
- Planlægning
- Procesovervågning og kontrol
- Vagtplaner eller tidsplaner
- Routing / køretøjsrute
- Planlægning
Referencer
- Michael R. Garey og David S. Johnson (1979). Computere og indtrængelighed: En guide til teorien om NP-fuldstændighed . WH Freeman. ISBN 0-7167-1045-5.