P versus NP

P versus NP is de volgende vraag die van belang is voor mensen die met computers en in de wiskunde werken: Kan elk opgelost probleem waarvan het antwoord snel door een computer kan worden gecontroleerd ook snel door een computer worden opgelost? P en NP zijn de twee soorten wiskundeproblemen waarnaar verwezen wordt: P-problemen zijn voor computers snel op te lossen, en worden dus als "gemakkelijk" beschouwd. NP-problemen zijn snel (en dus "gemakkelijk") door een computer te controleren, maar zijn niet noodzakelijk gemakkelijk op te lossen.

In 1956 schreef Kurt Gödel een brief aan John von Neumann. In deze brief vroeg Gödel of een bepaald NP-volledig probleem kon worden opgelost in kwadratische of lineaire tijd. In 1971 introduceerde Stephen Cook de precieze verklaring van het P versus NP probleem in zijn artikel "The complexity of theorem proving procedures".

Vandaag de dag wordt dit probleem door velen beschouwd als het belangrijkste open probleem in de informatica. Het is een van de zeven Millennium Prize Problems die door het Clay Mathematics Institute zijn geselecteerd en waaraan een prijs van 1.000.000 dollar is verbonden voor de eerste juiste oplossing.

Verduidelijkingen

Als u bijvoorbeeld een probleem hebt en iemand zegt: "Het antwoord op uw probleem is de verzameling getallen 1, 2, 3, 4, 5", dan kan een computer misschien snel uitvinden of het antwoord goed of fout is, maar het kan heel lang duren voor de computer zelf met "1, 2, 3, 4, 5" op de proppen komt. Een ander voorbeeld is het vinden van priemgetallen. Het is gemakkelijk om na te gaan of een getal priem is, maar het is heel moeilijk om die getallen überhaupt te vinden. Voor sommige van dit soort interessante, praktische vragen hebben we geen manier om snel een antwoord te vinden, maar als we een antwoord krijgen, is het mogelijk om het antwoord snel te controleren - dat wil zeggen, te verifiëren. Op deze manier kunnen NP-problemen worden beschouwd als raadsels: het kan moeilijk zijn om het antwoord op een raadsel te vinden, maar als men het antwoord eenmaal kent, lijkt het antwoord voor de hand te liggen. In deze vergelijking (analogie) is de basisvraag: zijn raadsels werkelijk zo moeilijk als we denken dat ze zijn, of zien we iets over het hoofd?

Omdat dit soort P versus NP vragen zo praktisch belangrijk zijn, willen veel wiskundigen, wetenschappers en computerprogrammeurs de algemene stelling bewijzen, dat elk snel op te lossen probleem ook snel op te lossen is. Deze vraag is belangrijk genoeg dat het Clay Mathematical Institute 1.000.000 dollar geeft aan iedereen die met succes een bewijs of een geldige verklaring levert die de stelling ontkracht.

Als we wat dieper graven, zien we dat alle P-problemen NP-problemen zijn: het is gemakkelijk te controleren of een oplossing juist is door het probleem op te lossen en de twee oplossingen te vergelijken. Men wil echter het omgekeerde weten: Bestaan er andere NP-problemen dan P-problemen, of zijn alle NP-problemen gewoon P-problemen? Als NP-problemen echt niet hetzelfde zijn als P-problemen (P ≠ NP), dan zou dat betekenen dat er geen algemene, snelle manieren kunnen bestaan om die NP-problemen op te lossen, hoe goed we ook zoeken. Echter, als alle NP problemen P problemen zijn (P = NP), dan zou dat betekenen dat er wel degelijk nieuwe, zeer snelle probleem-oplossingsmethoden bestaan. We hebben ze alleen nog niet gevonden.

Aangezien de beste pogingen van wetenschappers en wiskundigen nog geen algemene, gemakkelijke methoden hebben gevonden om NP-problemen op te lossen, geloven veel mensen dat er andere NP-problemen zijn dan P-problemen (dat wil zeggen dat P ≠ NP waar is). De meeste wiskundigen geloven ook dat dit waar is, maar op dit moment heeft nog niemand dit bewezen door middel van rigoureuze wiskundige analyse. Als bewezen kan worden dat NP en P hetzelfde zijn (P = NP is waar), zou dat een enorme invloed hebben op veel aspecten van het dagelijks leven. Daarom is het vraagstuk van P versus NP een belangrijk en veel bestudeerd onderwerp.

Voorbeeld

Stel dat iemand twee torens wil bouwen, door stenen van verschillende massa op elkaar te stapelen. Men wil er zeker van zijn dat elk van de torens precies dezelfde massa heeft. Dat betekent dat je de stenen op twee stapels met dezelfde massa moet leggen. Als men een verdeling van de stenen raadt waarvan men denkt dat die zal werken, kan men gemakkelijk controleren of men gelijk had. (Om het antwoord te controleren, kan men de stenen in twee stapels verdelen en vervolgens met een balans nagaan of ze dezelfde massa hebben). Omdat het gemakkelijk is om dit probleem, door computerwetenschappers "Partition" genoemd, te controleren - gemakkelijker dan het zonder meer op te lossen, zoals we zullen zien - is het geen P-probleem. []

Hoe moeilijk is het om dit op te lossen? Als men begint met slechts 100 stenen, zijn er 2^{100-1}-1 = 633.825.300.114.700.748.351.602.687, of ongeveer 6,3 x 10^{29} mogelijke manieren (combinaties) om deze stenen in twee stapels te verdelen. Als men elke dag één unieke combinatie van rotsen zou kunnen controleren, zou dat 1,3 x 10^{22} of 1.300.000.000.000.000.000.000 jaar inspanning vergen. Ter vergelijking: natuurkundigen denken dat het heelal ongeveer 1,4 x 10^{10} jaar oud is (450.000.000.000.000.000 of ongeveer 4,5 x 10^{17} seconden, of ongeveer één triljoenste zo oud als de tijd die nodig zou zijn voor onze inspanning om rotsen te stapelen. Dat betekent dat als men alle tijd neemt die sinds het begin van het heelal is verstreken, men elke seconde meer dan twee triljoen (2.000.000.000.000) verschillende manieren om de rotsen te verdelen zou moeten controleren, om alle verschillende manieren te controleren.

Als je een krachtige computer zou programmeren om al deze manieren om de rotsen te verdelen te testen, dan zou je met de huidige systemen misschien 1.000.000 {\displaystyle 1,000,000}combinaties per seconde kunnen controleren. Dit betekent dat er nog steeds 2.000.000 {\displaystyle 2,000,000}zeer krachtige computers nodig zijn, die al sinds het ontstaan van het heelal werken, om alle manieren om de rotsen te verdelen te testen.

Het kan echter mogelijk zijn een methode te vinden om de rotsen in twee gelijke stapels te verdelen zonder alle combinaties te controleren. De vraag "Is P gelijk aan NP?" is een steno voor de vraag of zo'n methode kan bestaan.

Waarom het belangrijk is

Er zijn veel belangrijke NP-problemen waarvan men niet weet hoe ze op te lossen op een manier die sneller is dan het testen van elk mogelijk antwoord. Hier zijn enkele voorbeelden:

  • Een reizende handelsreiziger wil 100 steden bezoeken door te rijden, waarbij hij zijn reis thuis begint en eindigt. Hij heeft een beperkte voorraad benzine, dus hij kan in totaal maar 10.000 kilometer rijden. Hij wil weten of hij alle steden kan bezoeken zonder zonder zonder benzine te komen staan.
  • Een school biedt 100 verschillende klassen aan, en een leraar moet voor het eindexamen van elke klas een uur kiezen. Om spieken te voorkomen, moeten alle leerlingen die een vak volgen het examen voor dat vak op hetzelfde tijdstip afleggen. Als een leerling meer dan één vak volgt, moeten al die examens op een ander tijdstip worden afgelegd. De leraar wil weten of hij alle examens op dezelfde dag kan plannen, zodat elke leerling het examen voor elk van zijn lessen kan afleggen.
  • Een boerin wil 100 watermeloenen van verschillende massa's naar de markt brengen. Ze moet de watermeloenen in dozen verpakken. Elke doos kan maar 20 kilo bevatten zonder te breken. De boerin wil weten of 10 dozen genoeg zijn om alle 100 watermeloenen naar de markt te brengen. (Dit is triviaal, als niet meer dan één watermeloen meer dan 2 kg weegt dan kunnen er 10 in elk van de kisten, als niet meer dan tien watermeloenen meer dan 2 kg wegen dan kan er van elk van hen één in elk van de kisten, enz. tot een snelle oplossing worden gebracht; observatie is de sleutel tot elke snelle oplossing zoals deze of het probleem van de getallenreeksen).
  • Een grote kunstgalerie heeft vele kamers, en aan elke muur hangen vele dure schilderijen. De eigenaar van de galerie wil camera's kopen om deze schilderijen in de gaten te houden, voor het geval een dief ze probeert te stelen. Hij wil weten of 100 camera's genoeg zijn om er zeker van te zijn dat elk schilderij door minstens één camera kan worden gezien.
  • Het kliekjesprobleem: De directeur van een school heeft een lijst met leerlingen die met elkaar bevriend zijn. Zij wil een groep van 10% van de leerlingen vinden die allemaal bevriend zijn met elkaar.

Exponentiële tijd

In het voorbeeld hierboven zien we dat met 100 {\displaystyle 100}stenen er 2 100 {\displaystyle 2^{100}}manieren zijn om de verzameling stenen te verdelen. Met n rotsen zijn ner 2 n {\displaystyle 2^{n}}combinaties. De functie f ( n ) = 2 n {{{n}} {\displaystyle f(n)=2^{n}}is een exponentiële functie. Ze is belangrijk voor NP omdat ze het slechtste aantal berekeningen weergeeft dat nodig is om een probleem op te lossen en dus ook de slechtste hoeveelheid tijd die nodig is.

En tot nu toe waren voor de moeilijke problemen berekeningen in de orde van grootte van 2 n {\displaystyle 2^{n}}{\displaystyle 2^{n}} nodig. Voor elk specifiek probleem hebben mensen manieren gevonden om het aantal benodigde berekeningen te verminderen. Men kan een manier bedenken om slechts 1% van het worst-case aantal berekeningen te doen en dat scheelt een hoop rekenwerk, maar dat is nog steeds 0,01 × ( 2 n ) {\displaystyle 0,01 maal (2^{n})}{\displaystyle 0.01\times (2^{n})} rekenwerk. En elke extra steen verdubbelt nog steeds het aantal berekeningen dat nodig is om het probleem op te lossen. Er zijn inzichten die methoden kunnen opleveren om nog minder berekeningen uit te voeren, waarbij variaties van het model worden gemaakt: b.v. 2 n / n 3 {\displaystyle 2^{n}/n^{3}} {\displaystyle 2^{n}/n^{3}}. Maar de exponentiële functie overheerst nog steeds als n {\displaystyle n}n groeit.

Beschouw het probleem van het inroosteren van examens (hierboven beschreven). Maar stel nu dat er 15000 studenten zijn. Er is een computerprogramma dat de roosters van alle 15000 studenten neemt. Het draait in een uur en maakt een examenrooster zodat alle studenten hun examens in een week kunnen maken. Het voldoet aan een heleboel regels (geen back-to-back examens, niet meer dan 2 examens in een periode van 28 uur, ...) om de stress van de examenweek te beperken. Het programma loopt een uur in de middagpauze en iedereen kent zijn/haar examenrooster met voldoende tijd om zich voor te bereiden.

Maar het volgende jaar zijn er 10 leerlingen meer. Als hetzelfde programma op dezelfde computer draait, wordt dat ene uur 2 10 {\displaystyle 2^{10}}uur, want elke extra leerling verdubbelt het rekenwerk. Dat zijn 6 {\displaystyle 6}weken! Als er 20 studenten meer waren, dan

2 20 {\displaystyle 2^{20}}uur = 1048576 {\displaystyle 1048576}uur ~ 43691 {\displaystyle 43691}dagen ~ 113 {\displaystyle 113}jaar

Dus, voor 15000 {\displaystyle 15000}leerlingen, duurt het een uur. Voor 15020 {\displaystyle 15020}leerlingen duurt het 113 {\displaystyle 113}jaar.

Zoals je kunt zien, groeien exponentiële functies erg snel. De meeste wiskundigen geloven dat de moeilijkste NP-problemen exponentiële tijd vergen om op te lossen.

NP-complete problemen

Wiskundigen kunnen aantonen dat er NP-problemen zijn die NP-Compleet zijn. Een NP-Compleet probleem is minstens zo moeilijk op te lossen als elk ander NP-probleem. Dit betekent dat als iemand een methode zou vinden om een willekeurig NP-Compleet probleem snel op te lossen, hij diezelfde methode zou kunnen gebruiken om elk NP probleem snel op te lossen. Alle hierboven genoemde problemen zijn NP-volledig, dus als de verkoper een manier heeft gevonden om zijn reis snel te plannen, kan hij dat aan de leraar vertellen, en zij kan diezelfde methode gebruiken om de examens te plannen. De boer zou dezelfde methode kunnen gebruiken om te bepalen hoeveel dozen ze nodig heeft, en de vrouw zou dezelfde methode kunnen gebruiken om een manier te vinden om haar torens te bouwen.

Omdat een methode die snel een van deze problemen oplost ze allemaal kan oplossen, zijn er veel mensen die er een willen vinden. Maar omdat er zoveel verschillende NP-complete problemen zijn en niemand tot nu toe een manier heeft gevonden om ook maar één ervan snel op te lossen, denken de meeste deskundigen dat het snel oplossen van NP-complete problemen niet mogelijk is.

Basiseigenschappen

In de computationele complexiteitstheorie is de complexiteitsklasse NP-complete (afgekort NP-C of NPC), een klasse van problemen die twee eigenschappen heeft:

  • Het behoort tot de reeks NP-problemen (niet-deterministisch polynomiale tijd): Elke gegeven oplossing van het probleem kan snel worden geverifieerd (in polynomiale tijd).
  • Het behoort ook tot de reeks NP-harde problemen: De problemen die minstens zo moeilijk zijn als de moeilijkste problemen in NP. Problemen die NP-hard zijn, hoeven geen elementen van NP te zijn; het kan zelfs zijn dat ze niet eens te ontcijferen zijn.

Formeel overzicht

NP-compleet is een deelverzameling van NP, de verzameling van alle beslissingsproblemen waarvan de oplossingen in polynomiale tijd kunnen worden geverifieerd; NP kan equivalent worden gedefinieerd als de verzameling van beslissingsproblemen die op een machine in polynomiale tijd kunnen worden opgelost. Een probleem p in NP is ook in NPC als en slechts als elk ander probleem in NP in polynomiale tijd in p kan worden omgezet. NP-compleet moest worden gebruikt als bijvoeglijk naamwoord: problemen in de klasse NP-compleet werden als NP+compleet problemen.

NP-complete problemen worden bestudeerd omdat het vermogen om snel oplossingen voor een probleem te verifiëren (NP) lijkt te correleren met het vermogen om snel probleem (P) op te lossen. Het is gebleken dat elk probleem in NP snel wordt opgelost-zoals de P = NP: probleemverzameling wordt genoemd. Het enkele probleem in NP-compleet is snel opgelost, sneller dan elk probleem in NP ook snel opgelost, omdat de definitie van een NP-compleet probleem stelt dat elk probleem in NP snel herleidbaar moet zijn tot elk probleem in NP-compleet (het is herleidbaar in polynomiale tijd). [1]

Voorbeelden

Het Booleaanse bevredigingsprobleem staat bekend als NP-volledig. In 1972 formuleerde Richard Karp 21 problemen waarvan bekend is dat ze NP-compleet zijn. Deze staan bekend als Karp's 21 NP-complete problemen. Zij omvatten problemen zoals het integer programmeringsprobleem, dat lineaire programmeringstechnieken toepast op de gehele getallen, het knapsack probleem, of het vertex cover probleem.


AlegsaOnline.com - 2020 / 2022 - License CC3