det åldrade P-kontra NP-problemet

så vad är då P-kontra NP-problemet?

för posten, status quo är att P NP.

p (polynomtid) avser klassen av problem som kan lösas av en algoritm i polynomtid. Problem i P-klassen kan sträcka sig från allt så enkelt som multiplikation till att hitta det största antalet i en lista. De är den relativt ”enklare” uppsättningen problem.

NP (icke-deterministisk polynomialtid) avser klassen av problem som kan lösas i polynomialtid av en icke-deterministisk dator., Detta är i huvudsak ett annat sätt att säga”om jag har obegränsad datorkraft (dvs så många datorer som jag behöver), kan jag lösa alla problem i högst polynom tid”. Mer intuitivt men det hänvisar till klassen av problem som för närvarande inte har något sätt att hitta en snabb (polynom tid) tillräckligt med svar, men kan snabbt verifieras (i polynom tid) om man ger lösningen på problemet. Termen verifierad här innebär att man kan kontrollera att den lösning som tillhandahålls verkligen är korrekt.

tydligt, baserat på definitionen ovan, s., Låt oss ta en titt på ett exempel för att illustrera detta abstrakta problem.

ett av de vanligaste men effektiva exemplen är Sudoku. Med tanke på ett olöst Sudoku-rutnät (9 x 9 till exempel) skulle det ta en algoritm en hel del tid att lösa en. Men om 9 x 9 rutnät ökar till en 100 x 100 eller 10,000 x 10,000 rutnät, den tid det skulle ta att lösa det skulle öka exponentiellt eftersom problemet i sig blir betydligt svårare., Men med tanke på ett löst Sudoku-rutnät (av 9 x 9) är det ganska enkelt att verifiera att den speciella lösningen verkligen är korrekt även om storleken vågar till 10 000 med 10 000. Det skulle vara långsammare, men tiden att kontrollera en lösning ökar i långsammare takt (polynomiellt).

det finns många andra NP-problem där ute, inklusive Knapsackproblemet och resande säljare problemet, och de är likartade genom att de är svåra att lösa men snabba att verifiera., Det grundläggande problemet vi försöker lösa här är:

kan vi snabbt känna igen NP-korrekta svar innebär att det också finns ett snabbt sätt att hitta dem?

om så är fallet (dvs. P=NP) kan detta kraftigt förändra hur vi ser på dessa NP-problem eftersom det betyder att det finns ett snabbt sätt att lösa alla dessa problem, bara att vi inte har kunnat räkna ut hur, ännu.

om detta inte är komplicerat nog, låt oss krydda upp det.,

bland dessa NP-problem finns det en kung av alla problem som forskare kallar NP-kompletta problem. Formellt är de en uppsättning problem för var och en av vilka något annat NP-problem kan minskas (adresseras nedan) i polynomtid och vars lösning fortfarande kan verifieras i polynomtid. Detta innebär att alla NP-problem kan omvandlas till ett NP-komplett problem.

informellt är de ”svåraste” av NP-problemen., Således, om någon NP-komplett problem kan lösas i polynom tid, då varje NP-komplett problem kan lösas i polynom tid, och varje problem i NP kan lösas i polynom tid (dvs P=NP). Det mest kända exemplet skulle vara resande säljare problemet.