• het probleem
• de oplossing
• samenvatting

Als u tijd doorbrengt in of rond de programmeergemeenschap, hoort u waarschijnlijk de term” P versus NP ” vrij vaak. Helaas, zelfs veel met formele computer science training hebben een zwak begrip van het concept.

Hier volgt een eenvoudige en beknopte uitleg:

het probleem

P VS.NP het probleem P vs. NP vraagt of elk probleem waarvan de oplossing snel kan worden geverifieerd door een computer ook snel kan worden opgelost door een computer., (Wikipedia)

dus laten we uitzoeken wat we bedoelen met P en NP.

P problemen zijn gemakkelijk op te lossen door computers, en NP problemen zijn niet gemakkelijk op te lossen, maar als je een potentiële oplossing presenteert is het gemakkelijk om te controleren of het correct is of niet.

zoals u kunt zien in het diagram hierboven, zijn alle P-problemen NP-problemen. Dat wil zeggen, als het gemakkelijk is voor de computer op te lossen, is het gemakkelijk om de oplossing te verifiëren. Dus het P vs NP probleem is gewoon de vraag of deze twee probleemtypen hetzelfde zijn, of dat ze verschillend zijn, dat wil zeggen dat er een aantal problemen zijn die gemakkelijk kunnen worden geverifieerd maar niet gemakkelijk kunnen worden opgelost.,

Het lijkt er momenteel op dat P ≠ NP, wat betekent dat we tal van voorbeelden hebben van problemen waarop we snel potentiële antwoorden kunnen verifiëren, maar die we niet snel kunnen oplossen. Laten we een paar voorbeelden bekijken:

• een reizende verkoper wil 100 verschillende steden bezoeken door thuis te rijden, te beginnen en te eindigen. Hij heeft een beperkte voorraad benzine, dus hij kan maar 10.000 kilometer rijden. Hij wil weten of hij alle steden kan bezoeken zonder dat de benzine op is., (uit Wikipedia)
• een boer wil 100 watermeloenen van verschillende massa ‘ s naar de markt brengen. Ze moet de watermeloenen in dozen verpakken. Elke doos kan slechts 20 kilogram bevatten zonder te breken. De boer moet weten of 10 dozen genoeg zijn voor haar om alle 100 watermeloenen op de markt te brengen. (uit Wikipedia)

al deze problemen hebben een gemeenschappelijk kenmerk dat de sleutel is tot het begrijpen van de intriges van P versus NP: om ze op te lossen moet je alle combinaties proberen.

de oplossing

daarom is het antwoord op de P vs., NP probleem is zo interessant voor mensen. Als iemand in staat zou zijn om aan te tonen dat P gelijk is aan NP, zou dat moeilijke problemen in de echte wereld triviaal maken voor computers.

samenvatting

1. P VS.NP behandelt de kloof tussen computers die in staat zijn om snel problemen op te lossen VS. alleen maar in staat zijn om voorgestelde oplossingen op juistheid te testen.
2. als zodanig is het P vs. NP probleem de zoektocht naar een manier om problemen op te lossen die het proberen van miljoenen, miljarden, of biljoenen combinaties vereisen zonder dat ze elk moeten proberen.,het oplossen van dit probleem zou ingrijpende gevolgen hebben voor de informatica, en dus voor onze samenleving.

Feb 7, 2017-Wikipedia-attributies toegevoegd.Maart 2, 2014-een deel van de verklaring opgeruimd om verwarring te voorkomen.

opmerkingen