Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111
Medan Hewlett-Packard rullar från Nedgången av sin CEO Mark Hurd går ner, företaget kan baska i ära av minst en potentiellt positiv prestation: En HP-forskare har erbjudit det han säger är en lösning på ett av de svåraste problemen inom datavetenskap.
HP Labs huvudforskare Vinay Deolalikar har lagt fram vad han hävdar är en lösning på vad som är allmänt känt som P-versus NP-problemet.
Så svårt är detta problem som Clay Mathematics Institute har lovat att tilldela den person som löser den USA 1 miljon dollar. Det är ett av endast sju problem, gemensamt känt som millennieprisproblemen, institutet har erbjudit denna bounty för. En av de sju, Poincaré-gissningen, löstes officiellt år 2006.
Det är ännu oklart om Deolalikar kommer att få pengar, eftersom Clay inte har sagt att den anser problemet lösas.
Detta problem, "en av De utestående problemen inom datavetenskap innebär att "avgöra om det finns frågor som kan besvaras snabbt, men som kräver en omöjligt lång tid att lösa genom ett direkt förfarande", förklarar en institutsida. I problemet står P för polynom tid och NP står för nondeterministisk polynom tid.
"Jag är glad att tillkännage ett bevis på att P inte är lika med NP", meddelade Deolalikar i en e-post till en grupp matteprofessorer, som sedan publicerades på söndag av Greg Baker, docent vid British Columbia Simon Fraser University.
I ett nötskal kan det här innebära att vissa problem bara kan lösas genom brute force-sökning, om lösningar kan hittas vid alla.
"Beviset krävde att man samlade principer från flera områden inom matematiken. Den stora ansträngningen för att bygga detta bevis var att avslöja en kedja av begreppsmässiga länkar mellan olika fält och visa dem genom en gemensam lins," skrev Deolalikar.
Naturligtvis tvekar de som är kunniga med problemet att proklamera att Deolalikar har löst problemet, med tanke på hur många kontroller som behöver göras. Och medan de berömmer Deolalikar för sitt grundliga tillvägagångssätt, en som skiljer sig från de mer slumpmässiga gissningar som vanligtvis presenteras, har ingen definitivt hävdat att han har knäckt problemet.
"Det verkar introducera några tankeväckande nya idéer, särskilt en koppling mellan statistisk fysik och den första ordens logiska karakteriseringen av NP ", skrev Scott Aaronson, assistent professor i elektroteknik och datavetenskap vid Massachusetts Institute of Technology, i en icke-kommittéblogg.
" Jag vet inte vad att tänka just nu, men jag är verkligen hoppfull ", skrev Dick Lipton, professor i datavetenskap vid Georgia Institute of Technology.
Joab Jackson täcker företagsprogramvara och generell teknik som bryter nyheter för IDG News Service. Följ Joab på Twitter på @Joab_Jackson. Joabs e-postadress är [email protected]
Misstänksama telefonsamtal på Skype skulle kunna riktas för att tappa som en del av en pan-europeisk nedbrytning av vilka lagmyndigheter anser att det är ett massivt tekniskt smuthull i gällande lagstiftningsregler som tillåter brottslingar att kommunicera utan rädsla för att bli överhettad av polisen. > Den europeiska utredningen skulle också kunna hjälpa amerikanska brottsbekämpande myndigheter att få tillgång till Internet-samtal. National Security Agency (NSA) är förstådd att tro att misstän
Medan polisen kan få en domstolsbeslut att trycka på en misstänkts landlinje och mobiltelefon, är det för närvarande omöjligt att få en liknande order för Internet-samtal på båda sidor om Atlanten.
Penguin Group har blivit den senaste bokförlaget för att nå en lösning med det amerikanska justitiedepartementet i en rättegång som påstår att apple och fem utgivare hade samarbetat för att höja ebook-priser.
Penguin Group har blivit den senaste bokutgivaren för att nå en lösning med US Department of Justice i en rättegång som hävdar att Apple och fem utgivare hade samarbetat för att höja ebook-priserna. Det föreslagna avtalsavtalet som inlämnats i USA: s tingsrätt för södra distriktet i New York, kommer Penguin att säga upp sina avtal med Apple och andra e-handelsbutiker och kommer att vara förbjudet i två år från att ingå nya avtal som begränsar återförsäljarens förmåga att erbjuda rabatter eller a
Med tiden kan du upptäcka att din Windows 8 Start-skärm kan sluta visa mycket kakel så att det ser ringa ut och svårt att hitta program genvägar. Det finns inget sätt att visa ännu mindre storlek på plattorna. Men Windows 8 erbjuder ett enkelt sätt att gruppera dessa programgenvägar, så att det blir mycket lättare att hitta dem. Om du faktiskt har många plattor på startskärmen, skulle gruppering av plattorna vara en fråga om städning till.
Gruppplattor på Windows 8 Startskärm