HP onderzoeker claimt complexiteitscundrum Crack Compsci

Terwijl Hewlett-Packard van haspelt de gevolgen van zijn CEO Mark Hurd die aftreedt, kan het bedrijf in de glorie van minstens één potentieel positieve verwezenlijking zonnebaden: Een onderzoeker van HP heeft aangeboden wat hij zegt een oplossing voor één van de moeilijkste problemen in computerwetenschap is

HP Labs hoofdonderzoeksonderzoeker Vinay Deolalikar heeft gepostuleerd wat volgens hem een ​​oplossing is voor wat algemeen bekend staat als het P versus NP-probleem.

Zo onhandelbaar is dit probleem dat het Clay Mathematics Institute heeft beloofd de persoon die het lost het VS toe te kennen $ 1 miljoen. Het is een van slechts zeven problemen, gezamenlijk bekend als de Millennium Prize Problems, waarvoor het instituut deze bounty heeft aangeboden. Een van de zeven, het vermoeden van Poincaré, werd in 2006 officieel opgelost.

Het is nog onduidelijk of Deolalikar het geld krijgt, omdat Clay niet heeft gezegd dat het probleem als opgelost beschouwt.

Dit probleem ", een van de de openstaande problemen in de informatica, "omvat" het bepalen of er vragen zijn waarvan het antwoord snel kan worden gecontroleerd, maar die een onmogelijk lange tijd nodig hebben om op te lossen via een directe procedure ", legt een instituutspagina uit. In het probleem staat P voor polynomiale tijd en NP staat voor niet-deterministische polynomiale tijd.

"Ik ben verheugd een bewijs aan te kondigen dat P niet gelijk is aan NP", kondigde Deolalikar aan in een e-mail aan een groep wiskundedocenten., die vervolgens werd gepost op zondag door Greg Baker, een universitair hoofddocent aan de Simon Fraser University in British Columbia.

Kort gezegd kan dit betekenen dat bepaalde problemen alleen kunnen worden opgelost door brute force search, als oplossingen kunnen worden gevonden op allemaal.

"Het bewijs vereiste het samenvoegen van principes uit meerdere gebieden binnen de wiskunde." De grootste inspanning bij het samenstellen van dit bewijs was het blootleggen van een keten van conceptuele verbanden tussen verschillende velden en het bekijken ervan door een gemeenschappelijke lens, "schreef Deolalikar.

Natuurlijk zijn degenen met kennis van het probleem aarzelen om te beweren dat Deolalikar het probleem heeft opgelost, gezien de hoeveelheid controles die zou moeten worden uitgevoerd. En hoewel ze Deolalikar prijzen voor zijn grondige aanpak, een die verschilt van de meer toevallige gissingen die gewoonlijk worden gepresenteerd, heeft niemand definitief beweerd dat hij het probleem heeft gebroken.

"Het lijkt een aantal tot nadenken stemmende nieuwe ideeën te introduceren, in het bijzonder een verband tussen statistische fysica en de eerste-orde logica karakterisering van NP, "schreef Scott Aaronson, een assistent-professor in elektrotechniek en computerwetenschappen aan het Massachusetts Institute of Technology, in een vrijblijvende bloginvoer.

" Ik weet niet wat om nu te denken, maar ik ben zeker hoopvol ", schreef Dick Lipton, professor in computerwetenschappen aan het Georgia Institute of Technology.

Joab Jackson behandelt bedrijfssoftware en algemeen nieuws voor De IDG-nieuwsdienst. Volg Joab op Twitter op @Joab_Jackson. Het e-mailadres van Joab is [email protected]