Den Alderen P versus NP Problem
Så hva er da P versus NP-problem?
For posten, status quo er at P≠NP.
P (polynomisk tid) refererer til klasse av problemer som kan løses av en algoritme i polynomisk tid. Problemer i S-klasse kan variere fra noe så enkelt som multiplikasjon for å finne det største tallet i en liste. De er relativt ‘lettere’ sett av problemer.
NP (ikke-deterministisk polynomisk tid) refererer til klasse av problemer som kan løses i polynomisk tid av en ikke-deterministisk datamaskinen., Dette er egentlig en annen måte å si «Hvis jeg har ubegrenset beregne makt (dvs. så mange datamaskiner som jeg trenger), jeg er i stand til å løse noe problem på de fleste polynomisk tid». Mer intuitivt skjønt, det refererer til klasse av problemer som i dag, har ingen mulighet til å finne en rask (polynomisk tid) nok svar, MEN kan raskt bli bekreftet (i polynomisk tid) hvis man gir løsningen på problemet. Begrepet bekreftet her betyr at man er i stand til å sjekke at løsningen er faktisk riktig.
Klart, basert på definisjonen ovenfor, S ⊆ NP., La oss ta en titt på et eksempel for å illustrere dette abstrakte problemet.
En av de mest vanlige, men effektiv eksempler er Sudoku. Gitt en uløst Sudoku rutenett (9 x 9, for eksempel), ville det ta en algoritme en god del tid til å løse en. Imidlertid, hvis den 9 x 9 rutenett øker til et 100 x 100 eller 10 000 x 10 000 rutenett, den tid det ville ta å løse det ville øke eksponentielt fordi problemet i seg selv blir betydelig vanskeligere., Imidlertid, gitt et løst Sudoku rutenett (9 x 9), den er ganske grei å kontrollere at den spesielle løsningen er faktisk riktig, selv om størrelsen skalaer til 10 000 av 10 000. Det vil være tregere, men tid til å sjekke en løsning øker ved en lavere pris (polynomially).
Det er mange andre NP problemer der ute, som Niste problem, og det Omreisende Selgere problem, og de er like i at de er vanskelige å løse, men raskt for å bekrefte., Det grunnleggende problemet vi prøver å løse her er:
Betyr å være i stand til å raskt gjenkjenne NP riktige svar betyr at det er også en rask måte å finne dem?
Hvis det er slik (dvs. P=NP), dette kan i stor grad endre hvordan vi ser på disse NP problemer fordi det betyr at det er en rask måte å løse alle disse problemene, bare at vi ikke har vært i stand til å finne ut hvordan, ENNÅ.
Hvis dette ikke er komplisert nok, la oss krydre det opp.,
Blant disse NP-problemer, det er en Konge over alle problemer som forskerne kaller NP-Komplette problemer. Formelt, de er et sett av problemer som hver andre NP problemet kan reduseres (adressert nedenfor) i polynomisk tid, og hvis løsning kan fortsatt bli bekreftet i polynomisk tid. Dette betyr at alle NP-problem kan bli forvandlet til et NP-Komplett problem.
Uformelt, de er de «vanskeligste» av NP-problemer., Dermed hvis et NP-Komplett problem kan løses i polynomisk tid, deretter hver NP-Komplett problem kan løses i polynomisk tid, og alle problemer i NP kan løses i polynomisk tid (dvs. P=NP). Det mest kjente eksempel ville være den Omreisende Selgere problem.
Det finnes også et sett av problemer som kalles NP-Harde problem., Disse problemene er minst like vanskelig som NP-problemer, men uten den tilstand som krever at det skal løses i polynomisk tid. Dette tyder på at NP-Hard problemer kan ikke nødvendigvis være en del av klassen NP. Et eksempel ville være å løse et sjakkbrett — gitt en tilstand av brettet, det er nesten umulig å fortelle hvis en gitt flytte på stat, er faktisk den optimale flytte. Formelt, det finnes ingen polynomisk tid-algoritme for å bekrefte en løsning på et NP-Harde problem.,
Hvis vi setter de to sammen, et NP-Komplett problem innebærer at det er NP-Hard, men en NP-Harde problem, betyr IKKE at det er NP-Komplett.
Definere NP-Kompletthet
Et problem L, er NP-Komplett hvis:
- L er NP-Hard
- L tilhører NP
diagrammet nedenfor (fokus på venstre side) skal gjøre ting klarere.,
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
Uformelt, et problem L1 kan bli redusert til et annet problem L2 hvis:
- Alle forekomster av L1 kan bli modellert som en forekomst av L2
- løsningen til det siste gir en løsning til tidligere og vice versa
for Å forstå dette intuitivt, som man kan tenke på det slik:
Hvis L1 er som kan reduseres til L2, L1, må være PÅ det MESTE så hardt som L2. I motsatt fall, L2 må være MINST like vanskelig som L1.
Matematisk, dette er benevnt som: L1 ≤p L2 (leses som «L1 er polynomially kan reduseres til L2»).,
