HP zit midden in een sex-schandaal, en daardoor zijn de koersen gekelderd. Maar nu is er ook een lichtpuntje opgedoken. Onderzoeker Vinay Deolalikar heeft bekend gemaakt dat hij een oplossing heeft gevonden voor het probleem dat algemeen bekend staat als het P-versus-NP probleem. Hij heeft zijn onderzoek wel los van HP gedaan.

Millennium Prize Problems

Het P-versus-NP probleem is van de zeven problemen die bekend staan als de Millennium Prize Problems. Het Clay Mathematics Institute heeft een premie in het vooruitzicht gesteld voor iedereen die een van deze problemen de wereld uit helpen. Een ervan, het Poincaré Conjecture probleem is in maart dit jaar officieel opgelost verklaard.

In een email van Vinay Deolalikar die zondag is gepost door Greg Baker van de Britisch Columbia Simon Fraser Universiteit zegt Deolalikar: “Ik heb het genoegen om een bewijs bekend te maken dat P niet gelijk is aan NP.” Dat doet hij in een 100 pagina's tellende paper.

P-versus-NP

P en NP zijn twee klassen problemen, en het P-versus-NP probleem stelt de vraag of deze klassen aan elkaar gelijk zijn. P-problemen zijn wiskundig op te lossen, en van NP-problemen is de oplossing makkelijk te controleren. Als deze twee klassen aan elkaar gelijk zijn, dan moeten problemen zoals beschreven in deze uitleg op een makkelijke manier op te lossen zijn die tot nu toe nog niet is ontdekt. Zijn de twee klassen niet aan elkaar gelijk, dan is het probleem alleen met brute force en wat geluk op te lossen.

Tot nu toe stonden twee partijen tegenover elkaar, de een die geloofde dat P en NP aan elkaar gelijk zijn, en de andere die geloofde dat ze niet aan elkaar gelijk zijn. Maar nu zegt Deolalikar dus dat hij het bewijs gevonden heeft dat P niet gelijk is aan NP, en dat er dus brute kracht nodig is om de problemen op te lossen.

1 Miljoen dollar

Het zal nog wel even duren voordat Deolalikar zijn miljoen dollar krijgt. De paper waarin hij zijn bewijs levert is 100 pagina’s groot en het bewijs maakt gebruik van principes uit verschillende gebieden van de wiskunde, zoals hij in zijn mail schrijft.

Volgens Scott Aaronson is het in ieder geval een heel degelijke paper, en in tegenstelling tot veel andere pogingen om het probleem op te lossen zitten er nieuwe ideeën in. Toch gelooft hij niet dat het probleem is opgelost. Als Vinay Deolalikar een miljoen dollar van het Clay Mathematics Institute krijgt, dan doet Aaronson er nog eens 200.000 dollar bovenop.

Bron: Techworld