Det Gamle p versus NP-Problem
så hvad er så P versus NP-problemet?
for posten er status .uo den P.NP.
P (polynomisk tid) henviser til klassen af problemer, der kan løses ved hjælp af en algoritme i polynomisk tid. Problemer i p-klassen kan variere fra alt så simpelt som multiplikation til at finde det største antal på en liste. De er den relativt ‘lettere’ sæt af problemer.NP (ikke-deterministisk polynomitid) henviser til klassen af problemer, der kan løses i polynomtid af en ikke-deterministisk computer., Dette er i det væsentlige en anden måde at sige “hvis jeg har ubegrænset computerkraft (dvs.så mange computere som jeg har brug for), er jeg i stand til at løse ethvert problem i højst polynomisk tid”. Mere intuitivt henviser det dog til den klasse af problemer, der i øjeblikket ikke har nogen måde at finde et hurtigt (polynomisk tid) nok svar, men kan hurtigt verificeres (i polynomisk tid), hvis man giver løsningen på problemet. Udtrykket verificeret her betyder, at man er i stand til at kontrollere, at den leverede løsning faktisk er korrekt.
klart, baseret på definitionen ovenfor, P N NP., Lad os se på et eksempel for at illustrere dette abstrakte problem.
et af de mest almindelige, men effektive eksempler er Sudoku. Givet en uløst Sudoku gitter (9 9 9 for eksempel), ville det tage en algoritme en hel del tid til at løse en. Men hvis 9 9 9 gitteret stiger til et 100 100 100 eller 10.000.10.000 gitter, vil den tid det tager at løse det stige eksponentielt, fordi problemet selv bliver betydeligt sværere., Men i betragtning af et løst Sudoku-gitter (af 9.9) er det ret ligetil at kontrollere, at den særlige løsning faktisk er korrekt, selvom størrelsen skaleres til 10.000 med 10.000. Det ville være langsommere, men tiden til at kontrollere en løsning øges langsommere (polynomisk).
Der er mange andre NP-problemer derude, herunder Knapsack-problemet og Traveling Salesmen-problemet, og de er ens, fordi de er svære at løse, men hurtige til at verificere., Det grundlæggende problem vi forsøger at løse her er:
Ikke at være i stand til hurtigt at genkende NP korrekte svar betyder, at der er også en hurtig måde at finde dem?
Hvis det er tilfældet (dvs P=NP), er dette i høj grad kan ændre, hvordan vi ser på disse NP problemer, fordi det betyder, at der er en hurtig måde til at løse alle disse problemer, blot at vi ikke har været i stand til at finde ud af, hvordan, ENDNU.
hvis dette ikke er kompliceret nok, lad os krydre det.,
blandt disse NP-problemer findes der en konge af alle problemer, som forskere kalder NP-komplette problemer. Formelt er de et sæt problemer, som hver især ethvert andet NP-problem kan reduceres (adresseret nedenfor) i polynomisk tid, og hvis løsning stadig kan verificeres i polynomisk tid. Dette betyder, at ethvert NP-problem kan omdannes til et NP-komplet problem.
uformelt er de de “sværeste” af NP-problemerne., Således, hvis et NP-Komplet problem kan løses i polynomiel tid, så hver NP-Komplet problem kan løses i polynomiel tid, og alle problemer i NP kan løses i polynomiel tid (dvs P=NP). Det mest berømte eksempel ville være problemet med rejsende sælgere.
Der findes også en række problemer, der kaldes NP-Hårde problemer., Disse problemer er mindst lige så hårde som NP-problemer, men uden den tilstand, der kræver, at den løses i polynomisk tid. Dette antyder, at NP-Hard-problemer muligvis ikke nødvendigvis er en del af NP-klassen. Et eksempel ville være at løse et skakbræt-i betragtning af en tilstand af et skakbræt er det næsten umuligt at se, om et givet træk i den givne tilstand faktisk er det optimale træk. Formelt findes der ingen polynomial tidsalgoritme til at verificere en løsning på et NP-hårdt problem.,
Hvis vi sætter de to sammen, betyder et NP-komplet problem, at det er NP-hårdt, men et NP-hårdt problem betyder ikke, at det er NP-komplet.
Definere NP-Fuldstændighed
Et problem, L, er NP-Komplet, hvis:
- L er NP-Hard
- L hører til NP
diagrammet nedenfor (med fokus på den venstre side) bør gøre tingene klarere.,
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
Uformelt, et problem L1 kan reduceres til et andet problem, L2, hvis:
- Enhver forekomst af L1 kan modelleres som et eksempel på L2
- Den løsning, at sidstnævnte giver en løsning til tidligere og vice versa
for At forstå dette intuitivt, kan man tænke på det som sådan:
Hvis L1 er reduceret til L2, L1 skal være så hårdt, som L2. Omvendt skal L2 være mindst lige så hård som L1.
matematisk betegnes dette som: L1 ≤P L2 (læses som “L1 er polynomisk reducerbar til L2”).,
