Wat is “P=NP?”, en waarom is het zo’n bekende vraag?

De vraag of P=NP misschien wel de meest bekende is in de hele computerwetenschap. Wat betekent het? En waarom is het zo interessant?

O, en voor extra waardering, plaats een bewijs van de waarheid of onwaarheid van de verklaring. 🙂

Antwoord 1, autoriteit 100%

P staat voor polynomiale tijd. NP staat voor niet-deterministische polynomiale tijd.

Definities:

• Polynomiale tijdbetekent dat de complexiteit van het algoritme O(n^k) is, waarbij n de grootte van uw gegevens is (bijv. het aantal elementen in een lijst dat moet worden gesorteerd) , en k is een constante.

• Complexiteitis de tijd die wordt gemeten in het aantal bewerkingen dat nodig is, als functie van het aantal gegevensitems.

• Bedieningis alles wat zinvol is als basishandeling voor een bepaalde taak. Voor het sorteren is de basishandeling een vergelijking. Voor matrixvermenigvuldiging is de basisbewerking vermenigvuldiging van twee getallen.

De vraag is nu, wat betekent deterministisch versus niet-deterministisch? Er is een abstract rekenmodel, een denkbeeldige computer die een Turingmachine (TM) wordt genoemd. Deze machine heeft een eindig aantal toestanden en een oneindige band met discrete cellen waarin een eindige reeks symbolen kan worden geschreven en gelezen. Op elk willekeurig moment bevindt het TM zich in een van zijn toestanden en kijkt het naar een bepaalde cel op de band. Afhankelijk van wat het uit die cel leest, kan het een nieuw symbool in die cel schrijven, de band één cel vooruit of achteruit verplaatsen en naar een andere toestand gaan. Dit wordt een toestandsovergang genoemd. Verbazingwekkend genoeg kun je door zorgvuldig toestanden en overgangen te construeren een TM ontwerpen, dat gelijk is aan elk computerprogramma dat kan worden geschreven. Daarom wordt het gebruikt als een theoretisch model om dingen te bewijzen over wat computers wel en niet kunnen doen.

Er zijn twee soorten TM’s die ons hier bezighouden: deterministische en niet-deterministische. Een deterministische TM heeft slechts één overgang van elke toestand voor elk symbool dat het van de band leest. Een niet-deterministische TM kan meerdere van dergelijke overgangen hebben, d.w.z. e. het is in staat om meerdere mogelijkheden tegelijk te controleren. Dit is een beetje zoals het spawnen van meerdere threads. Het verschil is dat een niet-deterministische TM zoveel van dergelijke “threads” kan spawnen als hij wil, terwijl op een echte computer slechts een bepaald aantal threads tegelijk kan worden uitgevoerd (gelijk aan het aantal CPU’s). In werkelijkheid zijn computers in feite deterministische TM’s met eindige banden. Aan de andere kant kan een niet-deterministische TM fysiek niet worden gerealiseerd, behalve misschien met een kwantumcomputer.

Het is bewezen dat elk probleem dat kan worden opgelost door een niet-deterministisch TM, kan worden opgelost door een deterministisch TM. Het is echter niet duidelijk hoeveel tijd het gaat kosten. De uitspraak P=NP betekent dat als een probleem polynomiale tijd kost op een niet-deterministische TM, men een deterministische TM kan bouwen die hetzelfde probleem ook in polynomiale tijd zou oplossen. Tot nu toe heeft niemand kunnen aantonen dat het kan, maar ook niemand heeft kunnen bewijzen dat het niet kan.

NP-volledig probleem betekent een NP-probleem X, zodat elk NP-probleem Y kan worden gereduceerd tot X door een polynoomreductie. Dat houdt in dat als iemand ooit met een polynomiale-tijd-oplossing voor een NP-volledig probleem komt, dat ook een polynomiale-tijd-oplossing zal geven voor elk NP-probleem. Dat zou dus bewijzen dat P=NP. Omgekeerd, als iemand zou bewijzen dat P!=NP, dan zouden we er zeker van zijn dat er geen manier is om een NP-probleem in polynomiale tijd op een conventionele computer op te lossen.

Een voorbeeld van een NP-compleet probleem is het probleem van het vinden van een waarheidstoewijzing die een booleaanse uitdrukking met n variabelen waar zou maken.
Op dit moment kan in de praktijk elk probleem dat polynomiale tijd kost op het niet-deterministische TM alleen in exponentiële tijd worden opgelost op een deterministisch TM of op een conventionele computer.
De enige manier om het waarheidstoewijzingsprobleem op te lossen, is bijvoorbeeld 2^n mogelijkheden te proberen.

Antwoord 2, autoriteit 24%

1. Een ja-of-nee probleem is in P(Polynomiale tijd) als het antwoord in polynomiale tijd kan worden berekend.
2. Een ja-of-nee-probleem is in NP(Non-deterministische Polynomiale tijd) als een ja-antwoord geverifieerdin polynomiale tijd.

Intuïtief kunnen we zien dat als een probleem in Pzit, het in NPzit. Gegeven een mogelijk antwoord op een probleem in P, kunnen we het antwoord verifiëren door het antwoord eenvoudig opnieuw te berekenen.

Minder voor de hand liggend, en veel moeilijker te beantwoorden, is of alle problemen in NPin Pzitten. Betekent het feit dat we een antwoord in polynomiale tijd kunnen verifiëren, dat we dat antwoord in polynomiale tijd kunnen berekenen?

Er is een groot aantal belangrijke problemen waarvan bekend is dat ze NP-compleet zijn (in principe, als bewezen is dat deze problemen in Pvoorkomen, dan alleNPproblemen zijn bewezen in P). Als P= NP, dan is bewezen dat al deze problemen een efficiënte (polynomiale tijd) oplossing hebben.

De meeste wetenschappers geloven dat P!=NP. Er is echter nog geen bewijs voor P= NPof P!=NP. Als iemand een bewijs levert voor beide vermoedens, zullen ze $ 1 miljoen winnen.

Antwoord 3, autoriteit 6%

Om het eenvoudigste antwoord te geven dat ik kan bedenken:

Stel dat we een probleem hebben waarvoor een bepaald aantal invoer nodig is en dat verschillende mogelijke oplossingen heeft, die het probleem voor bepaalde invoer al dan niet kunnen oplossen. Een logische puzzel in een puzzeltijdschrift zou een goed voorbeeld zijn: de inputs zijn de voorwaarden (“George woont niet in het blauwe of groene huis”), en de mogelijke oplossing is een lijst met uitspraken (“George woont in het gele huis”) huis, verbouwt erwten en is eigenaar van de hond”). Een beroemd voorbeeld is het handelsreizigersprobleem: gegeven een lijst met steden, en de tijden om van een stad naar een andere te komen, en een tijdslimiet, zou een mogelijke oplossing een lijst met steden zijn in de volgorde waarin de verkoper ze bezoekt, en het zou werken als de som van de reistijden minder was dan de tijdslimiet.

Zo’n probleem is in NP als we een mogelijke oplossing efficiënt kunnen controleren om te zien of deze werkt. Als we bijvoorbeeld een lijst met steden hebben die de verkoper in volgorde moet bezoeken, kunnen we de tijden voor elke reis tussen steden optellen en gemakkelijk zien of deze binnen de tijdslimiet valt. Een probleem is in P als we efficiënt een oplossing kunnen vinden als die bestaat.

(Efficiënt heeft hier een precieze wiskundige betekenis. Praktisch betekent dit dat grote problemen niet onredelijk moeilijk op te lossen zijn. Bij het zoeken naar een mogelijke oplossing zou een inefficiënte manier zijn om alle mogelijke mogelijke oplossingen op te sommen, of zoiets komt daar in de buurt, terwijl voor een efficiënte manier een veel beperktere set moet worden gezocht.)

Daarom kan het P=NP-probleem als volgt worden uitgedrukt: als je een oplossing voor een probleem zoals hierboven beschreven efficiënt kunt verifiëren, kun je dan efficiënt een oplossing vinden (of bewijzen dat die er niet is)? Het voor de hand liggende antwoord is: “Waarom zou je dat kunnen?”, en dat is zo’n beetje waar de zaak vandaag de dag voor staat. Niemand heeft het op de een of andere manier kunnen bewijzen, en dat stoort veel wiskundigen en informatici. Daarom krijgt iedereen die de oplossing kan bewijzen een miljoen dollar van de Claypool Foundation.

Over het algemeen nemen we aan dat P niet gelijk is aan NP, dat er geen algemene manier is om oplossingen te vinden. Als zou blijken dat P=NP, zou er veel veranderen. Cryptografie zou bijvoorbeeld onmogelijk worden, en daarmee elke vorm van privacy of verifieerbaarheid op internet. We kunnen immers efficiënt de versleutelde tekst en de sleutel nemen en de originele tekst produceren, dus als P=NP we de sleutel efficiënt zouden kunnen vinden zonder het van tevoren te weten. Het kraken van wachtwoorden zou triviaal worden. Aan de andere kant zijn er hele reeksen planningsproblemen en problemen met de toewijzing van middelen die we effectief zouden kunnen oplossen.

Misschien heb je de beschrijving NP-compleet gehoord. Een NP-compleet probleem is er een dat NP is (natuurlijk), en deze interessante eigenschap heeft: als het in P is, is elk NP-probleem dat, en dus P=NP. Als je een manier zou kunnen vinden om het Travelling Salesman-probleem efficiënt op te lossen, of logische puzzels uit puzzeltijdschriften, zou je alles in NP efficiënt kunnen oplossen. Een NP-compleet probleem is in zekere zin het moeilijkste soort NP-probleem.

Dus, als je een efficiënte algemene oplossingstechniek kunt vinden voor een NP-compleet probleem, of kunt bewijzen dat zoiets niet bestaat, dan zijn roem en fortuin van jou.

Antwoord 4, autoriteit 2%

Een korte samenvatting vanuit mijn bescheiden kennis:

Er zijn enkele eenvoudige rekenproblemen (zoals het vinden van het kortste pad tussen twee punten in een grafiek), die vrij snel kunnen worden berekend ( O(n^k), waarbij n de grootte van de invoer is en k een constante is (in het geval van grafieken is dit het aantal hoekpunten of randen)).

Andere problemen, zoals het vinden van een pad dat elk hoekpunt in een grafiek kruist of het verkrijgen van de RSA-privésleutel van de openbare sleutel, is moeilijker (O(e^n)).

Maar CS-spreken vertelt dat het probleem is dat we een niet-deterministische Turing-machine niet kunnen ‘converteren’ naar een deterministische, we kunnen echter niet-deterministische eindige automaten (zoals de regex-parser) transformeren in deterministische ( goed, dat kan, maar de looptijd van de machine zal lang duren). Dat wil zeggen, we moeten elk mogelijk pad proberen (meestal kunnen slimme CS-hoogleraren er een paar uitsluiten).

Het is interessant omdat niemand een idee heeft van de oplossing. Sommigen zeggen dat het waar is, anderen zeggen dat het niet waar is, maar er is geen consensus. Een ander interessant ding is dat een oplossing schadelijk zou zijn voor openbare/private sleutelcoderingen (zoals RSA). Je zou ze net zo gemakkelijk kunnen breken als het genereren van een RSA-sleutel nu is.

En het is een behoorlijk inspirerend probleem.

Antwoord 5, autoriteit 2%

Ik kan niet veel toevoegen aan het wat en waarom van het P=?NP-gedeelte van de vraag, maar met betrekking tot het bewijs. Een bewijs zou niet alleen wat extra krediet waard zijn, maar het zou ook een van de Millenniumproblemen. Er is onlangs een interessante peiling gehouden en de gepubliceerde resultaten (PDF)zijn zeker het lezen waard met betrekking tot het onderwerp van een bewijs.

Antwoord 6

Eerst enkele definities:

• Een bijzonder probleem doet zich voor in P als je een oplossing kunt berekenen in minder dan n^kvoor sommige k, waarbij nis de grootte van de invoer. Sorteren kan bijvoorbeeld worden gedaan in n log nwat kleiner is dan n^2, dus sorteren is polynomiale tijd.

• Er is een probleem in NP als er een kbestaat zodat er een oplossing van maximaal n^kbestaat die je tijdig kunt verifiëren op de meeste n^k. Neem 3-kleuring van grafieken: gegeven een grafiek, een 3-kleuring is een lijst van (vertex, kleur) paren met de grootte O(n)en u kunt tijdig verifiëren O(m)(of O(n^2)) of alle buren verschillende kleuren hebben. Een grafiek is dus alleen 3-kleurbaar als er een korte en gemakkelijk verifieerbare oplossing is.

Een equivalente definitie van NP is “problemen die kunnen worden opgelost door een Nondeterministische Turing-machine in Polynomiale tijd”. Hoewel dat je vertelt waar de naam vandaan komt, geeft het je niet hetzelfde intuïtieve gevoel van wat NP-problemen zijn.

Merk op dat P een deelverzameling van NP is: als je een oplossing in polynomiale tijd kunt vinden, is er een oplossing die kan worden geverifieerd in polynomiale tijd – controleer gewoon of de gegeven oplossing gelijk is aan de oplossing die je kunt vinden.

Waarom is de vraag P =? NPinteressant? Om dat te beantwoorden moet men eerst kijken wat NP-volledige problemen zijn. Simpel gezegd,

• Een probleem L is NP-compleet als (1) L in P zit, en (2) een algoritme dat L oplost, kan worden gebruikt om elk probleem L’ in NP op te lossen; dat wil zeggen, gegeven een instantie van L’ kunt u een instantie van L maken die een oplossing heeft als en alleen als de instantie van L’ een oplossing heeft. Formeel gesproken is elk probleem L’ in NP reduceerbaartot L.

Merk op dat de instantie van L polynoom-tijd berekenbaar moet zijn en polynoomgrootte moet hebben, in de grootte van L’; op die manier geeft het oplossen van een NP-volledig probleem in polynomiale tijd ons een polynomiale tijdoplossing voor alleNP-problemen.

Hier is een voorbeeld: stel dat we weten dat het 3 kleuren van grafieken een NP-moeilijk probleem is. We willen bewijzen dat het bepalen van de vervulbaarheid van booleaanse formules ook een NP-moeilijk probleem is.

Heb voor elk hoekpunt v twee booleaanse variabelen v_h en v_l, en de vereiste (v_h of v_l): elk paar kan alleen de waarden {01, 10, 11} hebben, die we kunnen beschouwen als kleur 1, 2 en 3.

Voor elke rand (u, v) geldt de eis dat (u_h, u_l) != (v_h, v_l). Dat wil zeggen,

not ((u_h and not u_l) and (v_h and not v_l) or ...)
alle gelijke configuraties opsommen en bepalen dat geen van beide het geval is.

ANDhet samenvoegen van al deze beperkingen geeft een booleaanse formule met een polynoomgrootte (O(n+m)). Je kunt controleren of het ook polynomiale tijd kost om te berekenen: je doet eenvoudige O(1)dingen per hoekpunt en per rand.

Als je de booleaanse formule kunt oplossen die ik heb gemaakt, dan kun je ook grafiekkleuring oplossen: laat voor elk paar variabelen v_h en v_l de kleur van v de kleur zijn die overeenkomt met de waarden van die variabelen. Door de formule te construeren, zullen buren niet dezelfde kleuren hebben.

Als driekleuren van grafieken dus NP-compleet zijn, is de booleaanse formule-tevredenheid dat ook.

We weten dat 3-kleuren van grafieken NP-compleet is; historisch zijn we dat echter te weten gekomen door eerst de NP-volledigheid van de booleaanse circuit-verzadigbaarheid aan te tonen, en dat vervolgens te reduceren tot 3-kleurbaarheid (in plaats van andersom).