NP-svært

Euler-Venn diagram for kompleksitetsklasserne P , NP , NP-Fuld og NP-hard

I kompleksitetsteori er NP - hårde eller NP - hårde problemer en klasse af problemer, der uformelt kan defineres som klassen af problemer , der er mindst lige så vanskelige som de sværeste problemer i kompleksitetsklasserne P og NP . Mere formelt er et problem NP-svært, hvis og kun hvis hvert NP -problem kan reduceres polynomielt til , det vil sige sådan, at . Det skal med andre ord kunne løses i polynomisk tid af en Turing-maskine udstyret med et orakel for . ^[1] Af denne definition følger det, at NP-svære problemer ikke er mindre vanskelige end NP-komplette problemer , som igen per definition er de sværeste af P/NP-klasserne. $H.$ $L$ $H.$ ${\ displaystyle L \ leq _ {T} H \; \; \ forall L \ i {\ tekst {NP}}}$ $L$ $H.$

Kategorien af NP-svære problemer, i modsætning til P, NP og NP-komplette klasserne, er ikke per definition begrænset til kun beslutningsproblemer ; faktisk er der også problemer med optimering og andre former.

Klassen af NP-svære problemer har stor teoretisk og praktisk relevans. I praksis betyder det at bevise, at et beregningsproblem svarer til et notorisk NP-svært problem, at bevise, at det praktisk talt er umuligt ^[2] at finde en effektiv måde at løse det på, hvilket har mange implikationer inden for datalogi . Fra et teoretisk synspunkt er studiet af NP-svære problemer et væsentligt element i forskningen i nogle af de vigtigste åbne problemer med kompleksitet.

Bemærkninger

Da NP-komplette problemer kan reduceres til hinanden i polynomiel tid, og alle problemer i NP kan reduceres til NP-komplette problemer i polynomiel tid, følger det, at givet et hvilket som helst NP-svært problem , er alle problemer i NP reducerbare i polynomiel tid til det. Følgelig, hvis der blev fundet en polynomisk-tidsløsning på et hvilket som helst NP-svært problem, kunne det bruges til at løse alle problemer i NP. Dette ville vise det . Selvom der endnu ikke er fundet beviser, mener det videnskabelige samfund generelt, at P og NP ikke er sammenfaldende. ^[3] $H.$ $P = NP$
Mere præcist: hvis , så har NP-svære problemer ingen polynomiel løsning. Omvendt, hvis det var sandt, at den polynomielle løselighed af NP-svære problemer ikke ville blive udledt af dette . $P \ neq NP$ $P = NP$
Hvis et optimeringsproblem H har en version L, hvor L er NP-komplet , så er H NP-svært;
Hvis H hører til NP , så er H også NP-komplet , fordi polynomiumreduktionen i dette tilfælde overholder kriterierne for en reduktion mellem NP-komplet problemer.

Eksempler

Et typisk NP-hårdt problem, beregningen af den korteste komplette vej i en graf

Et eksempel på et NP-svært problem er beslutningsproblemet kendt som delsum- problemet eller "SUBSET-SUM", og som svarer til spørgsmålet: givet et sæt af heltal, er der mindst én delmængde af det, som har nul algebraisk sum ? Et berømt NP-svært optimeringsproblem, som også har en meget stærk praktisk værdi, er at finde den Hamiltonske sti, der forbinder to punkter på en graf.

Der er beslutningsproblemer, der er NP-svære, men ikke NP-komplette, denne klasse inkluderer de problemer, der er i EXPTIME, det vil sige alle de beslutningsproblemer, der kan løses af en deterministisk Turing-maskine i tid O ( ) , hvor f (n) er en polynomiel funktion. Et problem er NP-hårdt, hvis alle problemer i NP kan reduceres polynomielt til det. Et eksempel på et NP-hårdt problem er det SAT -tilfredsstillende booleske formelproblem ). Det kan påvises, at NP-komplette problemer er polynomielt reducerede til dette problem (et bevis kendes f.eks. for 3sat ). Der er dog også eksempler på problemer, der er NP-svære, afgørelige, men ikke NP-komplette; et eksempel er problemet med at genkende TQBF -sproget ( True Quantified Boolean Formulas ). ${\ displaystyle 2 ^ {f (n)}}$

Alternativ definition

En alternativ definition af NP-hard , som ofte bruges, begrænser NP-Hard til beslutningsproblemer og bruger derfor polynomiel reduktion i stedet for Turing-reduktion. Formelt er et sprog L således NP-hårdt hvis . $\ forall L ^ {\ prime} \ i {\ mathbf {NP}}, L ^ {\ prime} \ leq _ {p} L$

NP-familienomenklaturkonventioner

Nomenklaturen af NP-problemer er forvirrende: NP-besværlige problemer er ikke i NP, på trods af at de er mærket med det navn. På trods af denne verbale modsigelse er dette navn nu i almindelig brug. På den anden side har NP -nomenklatursystemet en dybere betydning, som er af interesse for dets generiske kompleksitetsklasse, også kaldet NP .

NP-komplet - identificerer problemer, der er fuldstændige i NP.
NP-svær - identificerer problemer, der er mindst lige så komplekse som dem i NP (men hører ikke nødvendigvis til NP);
NP-simple - identificerer problemer, der i bedste fald er lige så komplekse som dem i NP (men ikke nødvendigvis hører til NP);
NP-ækvivalenter - identificerer problemer, der er nøjagtigt ækvivalente med NP, (men hører ikke nødvendigvis til NP);

Noter

^ Det vil sige udstyret med en hypotetisk mekanisme, der gør det muligt for den at have løsningen af problemet øjeblikkeligt . Hvis løsningen "fri" viser sig at være "billig" (se definitionen af polynomiumtid ), følger det, at den ikke kan være væsentligt enklere end . $H.$ $H.$ $L$ $H.$ $L$
^ Et af kompleksitetsteoriens åbne problemer er, om det er muligt at finde en effektiv algoritme (formelt: i polynomiel tid) for NP-komplette problemer. Det er derfor ikke teoretisk umuligt, at der kan findes en effektiv algoritme til at løse et NP-svært problem. Imidlertid er ingen sådan algoritme nogensinde blevet identificeret af det videnskabelige samfund, og generelt (selv i mangel af et matematisk bevis) er det tilbøjeligt til at tro, at et sådant resultat er umuligt.
^ Spørgsmålet "P = NP?" hører til årtusindets såkaldte problemer . Selvom den generelle tendens i det videnskabelige samfund er at tro, at svaret er "nej", er den modsatte hypotese også blevet formuleret af berømte matematikere som Kurt Gödel .

Bibliografi

Michael R. Garey og David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, 1979, ISBN 0-7167-1045-5 .

Eksterne links

( EN ) NP-difficile , i Encyclopedia Britannica , Encyclopædia Britannica, Inc.

[1] Det vil sige udstyret med en hypotetisk mekanisme, der gør det muligt for den at have løsningen af problemet øjeblikkeligt . Hvis løsningen "fri" viser sig at være "billig" (se definitionen af polynomiumtid ), følger det, at den ikke kan være væsentligt enklere end . $H.$ $H.$ $L$ $H.$ $L$

[2] Et af kompleksitetsteoriens åbne problemer er, om det er muligt at finde en effektiv algoritme (formelt: i polynomiel tid) for NP-komplette problemer. Det er derfor ikke teoretisk umuligt, at der kan findes en effektiv algoritme til at løse et NP-svært problem. Imidlertid er ingen sådan algoritme nogensinde blevet identificeret af det videnskabelige samfund, og generelt (selv i mangel af et matematisk bevis) er det tilbøjeligt til at tro, at et sådant resultat er umuligt.

[3] Spørgsmålet "P = NP?" hører til årtusindets såkaldte problemer . Selvom den generelle tendens i det videnskabelige samfund er at tro, at svaret er "nej", er den modsatte hypotese også blevet formuleret af berømte matematikere som Kurt Gödel .

[1]

[2]

[3]