tag:blogger.com,1999:blog-8131794231697217573.post5103505056513949570..comments2024-03-28T09:06:16.955+01:00Comments on Häggström hävdar: Scott Aaronsons underbara bok om kvantdatorberäkningarOlle Häggströmhttp://www.blogger.com/profile/07965864908005378943noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-8131794231697217573.post-39428899844411547322016-03-30T10:35:16.670+02:002016-03-30T10:35:16.670+02:00En källa till konstanta missuppfattningar är begre...En källa till konstanta missuppfattningar är begreppet “NP-problem,” som många icke-beräkningskomplexitetsteoretiker använder. (Jag har gott om tekniska fysiker bland mina algoritmikstudenter, som tydligen har belastats av den terminologin i förväg.)<br /><br />Jag försöker enbart prata om NP-svåra problem när jag pratar om hårdhet. NP-svåra är svåra. (NP-svårt betyder bara reducibilitet från 3-Sat, så begreppet kan introduceras utan att appellera till varken verifikation eller nondeterminism. Helt naturligt.) <br /><br />Medlemskap i NP däremot är ett mycket märkligt begrepp, som kräver verifikation eller nondeterminism. Det finns ingen bra svårhets-intution (både addition och hamiltonicitet hör till NP). Däremot finns det en (onaturlig) lätthets-intuition.<br /><br />Om jag någonsin blir ännu mer stringent tror jag att jag helt går bort från begreppet NP-problem eller medlemskap i NP. Det finns bara NP-lätta problem (existens av en polynomialtidsverifikator) och NP-svåra problem (reduktion från satisfierbarhet).<br /><br />NP-komplett är ett begrepp som jag helt undviker i undervisningen.Thore Husfeldthttps://www.blogger.com/profile/14937584058954877153noreply@blogger.comtag:blogger.com,1999:blog-8131794231697217573.post-85884543957472832222016-03-30T09:55:18.513+02:002016-03-30T09:55:18.513+02:00Jag har haft boken i min ägo ett tag efter ha hört...Jag har haft boken i min ägo ett tag efter ha hört Sean Carroll (fysikern) hylla den i något sammanhang. Jag har också lite matematik i bagaget men tycker hittills att den är tung (därmed inte sagt bra) för att vara populärvetenskap (vilket den iofs inte utger sig för att vara - den har väl sin grund i föreläsningsanteckningar?) Har man inte sin utbildning inom matematik/fysik/datalogi så är nog denna bok bortkastad.Henrikhttps://www.blogger.com/profile/15586351105605463903noreply@blogger.com