Hash Tables and Hash Functions
Mens Hewlett-Packard ruller fra Nedfallet av sin CEO Mark Hurd går ned, selskapet kan baske i ære av minst en potensielt positiv gjennomføring: En HP-forsker har tilbudt hva han sier er en løsning på et av de vanskeligste problemene innen datavitenskap.
HP Labs hovedforsker, Vinay Deolalikar, har skrevet ut hva han hevder er en løsning på det som er kjent som P versus NP-problemet.
Så vanskelig er dette problemet som Clay Mathematics Institute har lovet å tildele personen som løser den USA $ 1 million. Det er en av bare syv problemer, kollektivt kjent som tusenårsprisproblemer, instituttet har tilbudt denne geværet for. En av de syv, Poincaré-formodningen, ble offisielt løst i 2006.
Det er uklart om Deolalikar vil få penger, siden Clay ikke har sagt at den anser problemet løst.
Dette problemet, "en av De utestående problemene innen datavitenskap, "involverer" å avgjøre om det eksisterer spørsmål der svaret raskt kan kontrolleres, men som krever en umulig lang tid å løse ved en hvilken som helst direkte prosedyre, forklarer en instituttside. I problemet står P for polynomisk tid og NP står for nondeterministisk polynomisk tid.
"Jeg er glad for å kunngjøre et bevis på at P ikke er lik NP," rapporterte Deolalikar i en e-post til en gruppe matteprofessorer, som senere ble postet på søndag av Greg Baker, en lektor ved British Columbia Simon Fraser University.
I et nøtteskall kan dette bety at enkelte problemer kun kan løses ved brute force-søk, hvis det finnes løsninger på Alt.
"Beviset krevde å knuse sammen prinsipper fra flere områder innen matematikk. Den store innsatsen i å bygge dette beviset var å avdekke en kjede av konseptuelle lenker mellom ulike felt og vise dem gjennom en felles linse," skrev Deolalikar.
Selvfølgelig, de som er kunnskapsrike med problemet, nøler med å proklamere at Deolalikar har løst problemet, gitt antall kontroller som må gjøres. Og mens de roser Deolalikar for sin grundige tilnærming, en som adskiller seg fra de mer tilfeldige gjetningene som vanligvis presenteres, har ingen definitivt hevdet at han har sprakket problemet.
"Det synes å introdusere noen tankevekkende nye ideer, spesielt en sammenheng mellom statistisk fysikk og den første ordens logiske karakterisering av NP, "skrev Scott Aaronson, en assisterende professor i elektroteknikk og datavitenskap ved Massachusetts Institute of Technology, i en ikke-kommende bloggoppføring.
" Jeg vet ikke hva å tenke akkurat nå, men jeg er absolutt håpfull, "skrev Dick Lipton, professor i datavitenskap ved Georgia Institute of Technology.
Joab Jackson dekker bedriftsprogramvare og generell teknologi som bryter nyheter for IDG News Service. Følg Joab på Twitter på @Joab_Jackson. Joabs e-postadresse er [email protected]
Tidligere arbeidstaker som er dømt for å ødelegge bedriftsservere
En tidligere kontraktssystemadministrator vil tjene seks måneder i fengsel for sabotering av systemer ved sin tidligere arbeidsgiver etter ...
Korea DDOS-virusoppdrag flyttes til å ødelegge, slette data
Et datavirus som har lansert DDOS-angrep mot store nettsteder hele uken, vil Begynn å ødelegge data på vertsdatamaskiner på fredag, sa eksperter.
Forsker: Hackere kan begynne å misbruke elektriske billadere for å ødelegge rutenettet.
Hackere kan bruke sårbare ladestasjoner for å forhindre lading av elektriske kjøretøyer i et bestemt område, eller kanskje til og med bruke sårbarhetene til å kreme deler av strømnettet, sa en sikkerhetsforsker under Hack i Box-konferansen i Amsterdam på torsdag.