- Problem
- Løsningen
- Oversigt
Hvis du bruger tid på i eller omkring programmering samfund du nok høre udtrykket “P versus NP” ret hyppigt. Desværre har selv mange med formel datalogiuddannelse en svag forståelse af konceptet.
så her er en enkel og kortfattet forklaring:
problemet
p vs. NP P vs. NP-problemet spørger, om ethvert problem, hvis løsning hurtigt kan verificeres af en computer, også hurtigt kan løses af en computer., (ikikipedia)
så lad os finde ud af, hvad vi mener med P og NP.
p problemer løses let af computere, og NP-problemer kan ikke løses let, men hvis du præsenterer en potentiel løsning, er det let at kontrollere, om det er korrekt eller ej.
som du kan se fra diagrammet ovenfor, er alle p-problemer NP-problemer. Det vil sige, hvis det er nemt for computeren at løse, er det nemt at verificere løsningen. Så P vs NP-problemet spørger bare, om disse to problemtyper er de samme, eller om de er forskellige, dvs.at der er nogle problemer, der let kan verificeres, men ikke let løses.,
det ser i øjeblikket ud til, at P N NP, hvilket betyder, at vi har masser af eksempler på problemer, som vi hurtigt kan verificere potentielle svar på, men som vi ikke kan løse hurtigt. Lad os se på et par eksempler:
- en rejsende sælger ønsker at besøge 100 forskellige byer ved at køre, starte og afslutte sin rejse derhjemme. Han har et begrænset udbud af ben .in, så han kan kun køre i alt 10.000 kilometer. Han vil vide, om han kan besøge alle byerne uden at løbe tør for ben .in., (fra .ikipedia)
- en landmand ønsker at tage 100 vandmeloner af forskellige masser til markedet. Hun skal pakke vandmelonerne i kasser. Hver kasse kan kun holde 20 kg uden at bryde. Landmanden har brug for at vide, om 10 kasser vil være nok til, at hun kan bære alle 100 vandmeloner på markedet. (fra Wikipedia)
alle disse problemer har en fælles egenskab, der er nøglen til at forstå intrigen af P versus NP: for at løse dem skal du prøve alle kombinationer.
løsningen
Dette er grunden til svaret på P vs., NP problem er så interessant for folk. Hvis nogen var i stand til at vise, at P er lig med NP, ville det gøre vanskelige problemer i den virkelige verden trivielle for computere.
resum.
- P vs. NP omhandler kløften mellem computere, der hurtigt kan løse problemer vs. bare at kunne teste foreslåede løsninger for korrekthed.
- som sådan er p vs NP-problemet søgningen efter en måde at løse problemer, der kræver forsøg på millioner, milliarder eller billioner af kombinationer uden faktisk at skulle prøve hver enkelt.,
- løsning af dette problem ville have dybe effekter på computing og derfor på vores samfund.
7. Februar 2017-tilføjede attribikipedia-attributter.
2. marts 2014-ryddet op på noget af forklaringen for at undgå forvirring.