• problemet
• lösningen
• sammanfattning

om du spenderar tid i eller runt programmeringsgemenskapen hör du förmodligen termen ”P mot NP” ganska ofta. Tyvärr har även många med formell datavetenskaplig utbildning en svag förståelse för konceptet.

Så här är en enkel och kortfattad förklaring:

problemet

p vs NP p vs NP-problemet frågar om varje problem vars lösning snabbt kan verifieras av en dator också snabbt kan lösas av en dator., (Wikipedia)

så låt oss ta reda på vad vi menar med P och NP.

p problem löses enkelt av datorer, och NP-problem är inte lätt att lösa, men om du presenterar en potentiell lösning är det lätt att kontrollera om det är korrekt eller inte.

som du kan se från diagrammet ovan är alla P-problem NP-problem. Det är, om det är lätt för datorn att lösa, är det lätt att verifiera lösningen. Så P vs NP-problemet frågar bara om dessa två problemtyper är desamma, eller om de är olika, dvs att det finns några problem som lätt verifieras men inte lätt löses.,

det verkar för närvarande som om vi har många exempel på problem som vi snabbt kan verifiera potentiella svar på, men som vi inte kan lösa snabbt. Låt oss titta på några exempel:

• En resande säljare vill besöka 100 olika städer genom att köra, starta och avsluta sin resa hemma. Han har ett begränsat utbud av bensin, så han kan bara köra totalt 10 000 kilometer. Han vill veta om han kan besöka alla städer utan att få slut på bensin., (från Wikipedia)
• en bonde vill ta 100 vattenmeloner av olika massor till marknaden. Hon måste packa vattenmelonerna i lådor. Varje låda kan bara hålla 20 kilo utan att bryta. Bonden behöver veta om 10 lådor kommer att räcka för att hon ska bära alla 100 vattenmeloner till marknaden. (från Wikipedia)

alla dessa problem delar en gemensam egenskap som är nyckeln till att förstå intrigen av P mot NP: för att lösa dem måste du prova alla kombinationer.

lösningen

det är därför svaret på P vs., NP-problemet är så intressant för människor. Om någon kunde visa att P är lika med NP, skulle det göra svåra verkliga problem triviala för datorer.

sammanfattning

1. p vs NP behandlar klyftan mellan datorer som snabbt kan lösa problem vs. bara kunna testa föreslagna lösningar för korrekthet.
2. som sådan är p vs NP-problemet sökandet efter ett sätt att lösa problem som kräver försök av miljoner, miljarder eller trillioner kombinationer utan att behöva prova var och en.,
3. att lösa detta problem skulle ha djupgående effekter på databehandling, och därmed på vårt samhälle.

Feb 7, 2017 — Lagt till Wikipedia befogenheter.
2 mars 2014-städade upp en del av förklaringen för att undvika förvirring.

anmärkningar