• Problemet
• Løsningen
• Oppsummering

Hvis du tilbringer tid i eller rundt programmering samfunnet du sannsynligvis høre begrepet «P versus NP» ganske ofte. Dessverre, selv med mange formelle computer science trening har en svak forståelse av begrepet.

Så her er en enkel og kortfattet forklaring:

Problemet

P vs NP P vs NP problem spør om alle problemer hvis løsning kan være raskt bekreftet av en datamaskin, kan også være raskt løst ved en datamaskin., (Wikipedia)

Så la oss finne ut hva vi mener med P og NP.

P problemer er lett løses ved hjelp av datamaskiner, og NP-problemer er ikke lett lar seg, men hvis du presentere en mulig løsning er det enkelt å kontrollere om det er riktig eller ikke.

Som du kan se av diagrammet ovenfor, alle P problemer er NP-problemer. Det er, hvis det er lett for datamaskinen til å løse, det er lett å verifisere løsningen. Så P vs NP problemet er bare å spørre hvis disse to problem typer er de samme, eller dersom de er ulike, dvs. at det er noen problemer som er lett verifisert, men ikke lett løses.,

Det foreløpig ut til at P ≠ NP, som betyr at vi har nok av eksempler på problemer som vi kan raskt kontrollere potensielle svar på, men som vi ikke kan løse raskt. La oss se på et par eksempler:

• En omreisende selger ønsker å besøke 100 forskjellige byer ved kjøring, starter og slutter sin tur hjemme. Han har en begrenset tilførsel av bensin, så han kan bare drive totalt 10 000 kilometer. Han ønsker å vite om han kan besøke alle byene uten å gå tom for bensin., (fra Wikipedia)
• En bonde ønsker å ta 100 vannmeloner av forskjellige massene til markedet. Hun trenger å pakke vannmeloner i bokser. Hver boks kan bare holde 20 kilo uten å bryte. Bonden trenger å vite om 10 bokser vil være nok for henne å bære alle 100 vannmeloner til markedet. (fra Wikipedia)

Alle av disse problemene dele en felles karakteristikk som er nøkkelen til å forstå intriger av P versus NP: for å løse dem må du prøve alle kombinasjoner.

Løsningen

Dette er grunnen til at svaret på P vs., NP-problemet er så interessant for folk. Hvis noen var i stand til å vise at P er lik NP, det ville gjøre vanskelige problemer i den virkelige verden trivielt for datamaskiner.

Oppsummering

1. P vs NP avtaler med gapet mellom datamaskiner blir i stand til å raskt løse problemer vs. bare å være i stand til å teste løsninger for korrekthet.
2. et eksempel P vs NP-problemet er å finne en måte å løse problemer som krever prøver av millioner, milliarder, eller billioner av kombinasjoner uten faktisk å måtte prøve hver og en.,
3. Løse dette problemet ville ha dyptgripende virkninger på data, og derfor på vårt samfunn.

Feb 7, 2017 — Lagt Wikipedia attribusjoner.
2 Mars 2014 — Ryddet opp i noen av forklaringen for å unngå forvirring.

Notater