Hmm
"De så f.eks., at regnestykket 12x2 er lettere at løse end 122"
Det skal vel ikke være 122 men 12^2
Indisk matematiker får på puklen for at sige P er ikke lig NP
Matematikere og dataloger verden over har i disse dage noget at snakke om. Det største og mest berømte uløste problem inden for den teoretiske datalogi er påstået løst af Vinay Deolalikar fra HP Labs i Californien. I et 103 sider langt bevis, nu lagt online på scribd, skriver Deolalikar, at han har vist, at P ikke er lig NP - en efterhånden ikonisk ligning, der kort fortalt går ud på, at der findes fundamentale og uovervindelige forskelle i sværhedsgraden af matematiske problemer.
Hvis Deolalikars bevis er korrekt, venter der en check på en million dollar fra Clay Mathematics Institute, idet spørgsmålet om P=NP er en af resterende seks Millennium Prize-opgaver, som matematikere verden over ønsker at se løst. Men siden beviset blev offentliggjort 6. august, har en række førende matematikere allerede fundet flere huller og uklarheder. Ikke desto mindre mener man, at beviset indeholder tilpas mange nye ideer og perspektiver til, at det fortjener at blive diskuteret, selv om det er forkert.
P-problemer
Spørgsmålet om P=NP eller ej, har både fundamentale filosofiske og helt konkrete implikationer for computer- og kompleksitetsforskningen. Men hvad betyder P og NP egentlig?
I 1960'erne begyndte dataloger at ordne matematiske problemer i forhold til, hvor mange operationer eller antal regnetrin, der skal til for at løse dem. De så f.eks., at regnestykket 12x2 er lettere at løse end 122, fordi en fordobling af et vilkårligt tal med k cifre kræver, at man ganger hvert enkelt ciffer med to, hvorimod en kvadrering normalt kræver, at man ganger hvert ciffer med hvert ciffer. Antallet af regnetrin for en fordobling er altså ligefrem proportional med k, hvorimod antallet af regnetrin for en kvadrering er proportional med k2.
Endnu sværere regnestykker kræver k3 eller k4 trin, hvilket svarer til en polynomiel stigning i antallet af regneoperationer på en computer. De fleste normale regnestykker fra gymnasiet er af den beskaffenhed, og matematikerne siger, at de er 'af polynomiel art' eller 'af typen P'.
NP-problemer
Men der findes også problemer, som er meget sværere at løse, for eksempel opgaven 'find et tal som går op i 1.050.504.368.559.379, og det må ikke være tallet 1 eller tallet selv'. Hvis man vil prøve lykken, må man regne med oddset én ud af 30 millioner, hvilket er en del sværere end at vinde i lotto. Det skyldes, at 1.050.504.368.559.379 kun er et produkt af to tal, nemlig primtallene 18.712.789 og 56.138.311, altså tal, som kun kan deles med sig selv og 1.
Der findes ingen deterministiske metoder, hvormed man konsistent kan løse den slags NP-opgaver hurtigt, end ikke på computere, og gudskelov for det, for krypteringsteknikkernes sikkerhed på bl.a. internettet afhænger af det. Man kalder denne form for matematiske problemer for NP-problemer, hvilket står for 'nondeterministic polynomial'. Det skyldes, at man endnu ikke har fundet nogen effektiv deterministisk metode, hvormed man kan løse dem på samme måde, som man kan løse problemer af typen P. Man kan gætte og være heldig - eller få et surt arbejde.
Men ikke desto mindre er de meget vigtige for en række praktiske problemer: Hvordan finder man den optimale måde, hvormed industrimaskiner kan operere på et givent område? Hvordan koordineres hjemmeservice bedst? Hvordan løser man et vanskeligt puslespil? Eller en sudoku? Eller her den klassiske: Hvordan bruger en handelsrejsende mindst muligt benzin, hvis han pendler mellem k forskellige byer? Alle disse problemer er NP-problemer, men måske er de i virkeligheden blot problemer af typen P, hvor vi bare endnu ikke kender beregningsmetoden?
Ingen grænseløs erkendelse
Afgørende i denne sammenhæng er, at mange NP-problemer er såkaldt 'NP-komplette', hvilket betyder, at hvis man først har vist, at ét NP-komplet problem (som f.eks. den handelsrejsende) er af typen P, så er alle andre NP-problemer det også. Selv om der findes et utal af NP-komplette problemer, har man ikke fundet nogen effektiv løsningsformel for en eneste af dem.
Deolalikar mener at kende svaret, og svaret er at det vil man aldrig kunne. P er ikke lig NP. Man kan altså ikke reducere NP-problemer til P-problemer. Hans bevis, hvis rigtigt, betyder, at selv om der findes simple løsninger til svære gåder, kan de end ikke principielt findes ad rationel vej. Vi kan kun håbe på held og kreativitet. Ligesom det var tilfældet med Gödels ufuldstændighedsteorem, vil den stadig udbredte tro på, at den matematisk-naturvidenskabelige metode besidder nøglen til grænseløse erkendelse, endnu engang blive gendrevet.
Kritikken er hård
Deolalikar sendte sit paper rundt blandt kolleger, inden det var gået igennem peer review, hvilket er ved at blive almindelig praksis, hvis man ønsker at få hurtig feedback. Og den er bestemt ikke udeblevet. I løbet af de sidste uger har hundreder af matematikere og dataloger diskuteret beviset på blogs og via e-mail. Meget af trafikken er gået igennem Georgia Tech-datalogen Richard Liptons blog. Tidligere professor i kvanteinformation ved University of Queensland Michel Nielsen har lavet en wiki, som forsøger at samle argumenterne fra de mange tråde og underdiscipliner.
Flere matematikere mener nu, at der er alt for store mangler. Især støder det, at beviset ikke virker for matematiske problemer, som er i sværere kompleksitetsklasser kaldet 2SAT eller XOR-SAT, selv om man ved at, der findes algoritmer for dem, som kan løses i polynomial tid.
Også Neil Immerman fra University of Massachusetts siger i en e-mail, at han har fundet en alvorlig fejl i Deolalikars paper.
Deolalikar forsøger at bevise, at nogle problemer er i NP-klassen uden at være i P-klassen ved at bruge en anden matematisk klasse kaldet FO(LFP). Men ifølge Immerman kan denne klasse ikke bruges på den måde, fordi man så ikke vil kunne dække alle P.
Scott Aaronson fra MIT mener, at der er mindst otte tegn på, at beviset er forkert, og han har endda satset sine egne sparepenge på det:
»Hvis Vinay Deolalikar modtager den en million dollar doterede Clay Millenium Prize for sit bevis på, at P ikke er lig NP, vil jeg, Scott Aaronson, personligt supplere prisen med 200.000 dollar,« skriver han på sin blog.
Terence Tao fra UCLA mener dog, at Deolalikars overordnede strategi endnu ikke har vist sig at være helt håbløs:
Selv om det viser sig, at man ikke kan redde beviset, selv med store reparationer, så er det stadig tænkeligt, at selve strategien er god nok.
Under alle omstændigheder viser debatten, at frontforskning kan gøres på en anden og mere spændende måde end fagblade og lange forelæsninger - nemlig via debatfora, blogs, wikis og et aktivt og åbent forskningsmiljø på internettet.
Læs også
Et par kommentarer
En lettere uformel, og ikke helt korrekt måde at beskrive problemet på er: NP er en klasse af problemer, hvor det bedste vi kan gøre er at lave brute-force-søgning. Computeren konstruerer altså en løsning ved at prøve sig frem gennem alle kombinationsmuligheder og så tage "den bedste" for hvad det så end er i den givne situation. Vi kender ikke bedre algoritmer for disse problemer.
Spørgsmålet er så bare om der et eller andet sted derude i datalogiens og matematikkens verden findes en smartere måde at gøre det på, så vi kan undgå at skulle søge (for det er hulens dyrt). Hvis der gør er P = NP. Hvis ikke, så er P /= NP. Da rigtigt mange af de interessante problemer her i verden som vi godt vil have løst er i NP-klassen, så kunne det være rart med en afklaring.
Deolalikars påståede bevis er at klassificere hele P-klassen af problemer og så vise at de har en bestemt struktur. Dernæst tager han k-SAT som er et kendt NP problem og viser at k-SAT ikke har denne struktur. Resultatet er altså at der findes et problem i NP (k-SAT) som ikke kan være i P og dermed må P /= NP.
Problemet med 2SAT og XOR-SAT er følgende: Begge disse problemer er kendte P-problemer. Så hvis beviset virker, så skal det kunne splitte dem fra k-SAT. Ellers vi har lige vist at 2-SAT ikke har strukturen der klassificerer alle P-problemer - og det er en modstrid. Beviset vil derfor falde sammen. Artiklen tager altså fejl på dette område (Se f.eks. wikipedia-artiklen for 2-satisfiability).
Rent meta-bevis, så er problemet at Deolalikars bevis er for "kraftfuldt". Det viser mere end hvad det lige skal i visse dele af beviset. Nuvel, dette er ikke altid lig med at beviset er forkert, men det er en advarselslampe. Richard Liptons blog er værd at læse på det punkt. Han har en længere udredning om det fra for et par dage siden. Et andet eksempel er at du fører bevis under antagelser A, B og C, men når beviset er ovre, så har B aldrig været i spil. Det betyder enten at B er overflødig, eller at dit beivs har en fejl.
Kvante-computere og NP
Så vidt jeg har forstået det, så kan NP-problemer ikke løses med en computer. Men gælder det også for kvante-computere?
De findes ganske vist ikke rigtig endnu, men måske det er muligt at sige noget om det alligevel - ud fra den principielle funktionsmåde for en kvante-computer.
Poul-Henning Kamp
Blogger
Re: Kvante-computere og NP
Så vidt jeg har forstået det, så kan NP-problemer ikke løses med en computer. Men gælder det også for kvante-computere?
Nogle af dem kan løses med sejlgarn.
Travelling Salesman problemet kan f.eks løses ved at du laver et "landkort" af sammenbundne snore, således at knuderne repræsenterer byerne og snorenes længder er proportionale til distancen imellem dem.
Når du så skal finde den korteste afstand fra A til B, tager du A-knuden i den ene hånd og B-knuden i den anden og trækker indtil der imellem dem er en udspændt snor med et antal knuder på.
Konstruktionen af snore-kortet er O(n) og selve opslaget er O(1) performance, det kan dårligt blive billigere.
Poul-Henning
Re: Kvante-computere og NP
Så vidt jeg har forstået det, så kan NP-problemer ikke løses med en computer. Men gælder det også for kvante-computere?
Det simpleste NP-problem, jeg kender, er, at man har en liste af tal, og skal afgøre, om summen af et udvalg af tallene giver 0.
Fx om summen af 1 eller flere af tallene {1, -5, 4, -8, 3, -19, 22, -15, 13, -9, 11} giver 0.
Re: Kvante-computere og NP
@Poul-Henning: Problemet, du der løser, er meget simplere, nemlig single-pair shortest path. Dijkstras algoritme løser det mere generelle problem, single-source-shortest path (find korteste veje fra A til alle andre) i tid O(|E| + |V|), hvor |E| antallet af kanter (veje) i grafen og |V| er antallet af knuder (byer). Din algoritme bruger lige så lang tid. Dijkstras algoritme sikrer også at data flyder hurtigst muligt rundt på internettet (se OSPF routing protokollen).
TSP (traveling salesman problem) kræver, du kommer rundt til alle |V| byer med den korteste rute. En simpel løsning på dette problem er at prøve alle vejkombinationer og teste hvad de koster. Der er 2^|E| vejkombinationer og det tager O(|E|) tid at teste hver af dem, hvilket giver os O(|E|*2^|E|). Dette kan forbedres, men man kommer ikke under en eksponentiel faktor medmindre P=NP.
Som et kuriosum kan nævnes at rutefindingsalgoritmer ikke bruger Dijkstras algoritme direkte, da den er alt for ineffektiv for store kort (der er ret mange veje i verden). I stedet bruges an A*-heuristik, som essentielt siger, hvis vi skal fra Århus til Esbjerg, prøver vi først vej-afsnit, der direkte bringer os tætter på Esbjerg, og kommer dermed ikke til at tage veje over fx Fyn i betragtning. Der er lidt flere detaljer, men afhængigt af implementationen garanterer denne algoritme ikke, man finder den BEDSTE vej, blot at man finder en GOD vej. (Man kan modificere algoritmen til at finde den bedste vej, også hurtigere end generelt at bruge Dijkstra.)
Dette illustrerer også hvorfor det ikke rigtigt har den store praktiske værdi at vide om P = NP – til alle problemer vi møder i praksis findes heuristikker, som for det meste løser problemet godt nok. Selv hvis P = NP, vil eksponenten formenteligt være stor, da dataloger har arbejdet intenst med problem i adskillige år uden at finde en løsning, hvilket gøre en uanvendelig i praksis.
Så vidt jeg har forstået det, så kan NP-problemer ikke løses med en computer. Men gælder det også for kvante-computere?
Det gør det ikke. Fx heltalsfaktorisering kan gøres i polynomiel tid. I 2001 blev 15 faktoriseret på en 7-bits kvantecomputer. De fik det rigtige resultat og super-hurtigt ;-)
Eksterne links
Call me lazy, men jeg syntes faktisk det var meget rart med eksterne kildehenvisninger i slutningen af artiklerne..
Evt. link til beviset på scribd, link til Millennium Prize-opgaverne og en matematisk gennemgang af P=NP ville gi' lidt mere dybde.
Eksterne links
Call me lazy, men jeg syntes faktisk det var meget rart med eksterne kildehenvisninger i slutningen af artiklerne..
Evt. link til beviset på scribd, link til Millennium Prize-opgaverne og en matematisk gennemgang af P=NP ville gi' lidt mere dybde.
Re: Kvante-computere og NP
Så vidt jeg har forstået det, så kan NP-problemer ikke løses med en computer. Men gælder det også for kvante-computere?
Joda, men først en lille korrektion til artiklen, som jeg får brug for: Det der i artiklen er beskrevet som de NP-komplette problemer (eng. NP-complete) hedder normalt NP-fuldstændige i den danske litteratur.
Så til spørgsmålet. Kvantecomputere splitter NP-klassen. Der findes problemer i NP-klassen som lader sig effektivt løse med en kvantecomputer. Men der findes imidlertid også problemer hvor det ikke vides om en kvantecomputer giver en effektiv løsning.
Primtalsfaktorisering, som nævnes i artiklen, kan effektivt løses på en kvantecomputer via Shors algoritme. Kvante-algoritmen giver en effektiv metode til at finde en (primtals-)faktor. Formelt ligger Shors algoritme i klassen BQP (Bounded-error Quantum Polynomial time).
Men for de NP-fuldstændige problemer vides det ikke hvorvidt de har en effektiv kvantealgoritme til at løse dem. Det er stadigt et åbent spørgsmål, men noget tyder på at det ikke er tilfældet. Med andre ord kan vi på nuværende tidspunkt effektivt løse visse NP-problemer, men ikke andre.
Desværre er der nogen som påstår at kvantecomputere får hele NP-hierarkiet til at kollapse - og det er ikke tilfældet. Kvantecomputere kan heller ikke søge som en nondeterministisk Turingmaskine - hvis det var tilfældet ville hierarkiet kollapse på samme vis.
Re: Kvante-computere og NP
NP-problemer kan sagtens løses med en computer. Men når problemstørrelsen bliver "stor nok", så bliver det så beregningstungt at det ikke kan lade sig gøre. Problemet med NP-klassen er at den har eksponentiel udvikling. Tilføjelsen af en ekstra variabel til probleminstansen betyder dobbelt så lang beregningstid som et minimum.
Men bare fordi problemerne er svære, så betyder det ikke at de er umulige at løse. Og der er en masse forskning som handler om netop dette: Knæk problemerne så godt vi nu kan gøre det.
Lasses problem, kaldet SUBSET-SUM er et såkaldt pseudo-polynomielt problem. Det er i NP-klassen men hører til i den "lettere ende". Vi har nogle rimeligt effektive løsere for problemer af denne type. Hvis du bare vil have en tilnærmet løsning findes der også approximative algoritmer. Disse garanterer typisk en eller anden fejlrate fra den optimale løsning.
Re: Kvante-computere og NP
Så vidt jeg har forstået det, så kan NP-problemer ikke løses med en computer. Men gælder det også for kvante-computere?
Joda, men først en lille korrektion til artiklen, som jeg får brug for: Det der i artiklen er beskrevet som de NP-komplette problemer (eng. NP-complete) hedder normalt NP-fuldstændige i den danske litteratur.
Så til spørgsmålet. Kvantecomputere splitter NP-klassen. Der findes problemer i NP-klassen som lader sig effektivt løse med en kvantecomputer. Men der findes imidlertid også problemer hvor det ikke vides om en kvantecomputer giver en effektiv løsning.
Primtalsfaktorisering, som nævnes i artiklen, kan effektivt løses på en kvantecomputer via Shors algoritme. Kvante-algoritmen giver en effektiv metode til at finde en (primtals-)faktor. Formelt ligger Shors algoritme i klassen BQP (Bounded-error Quantum Polynomial time).
Men for de NP-fuldstændige problemer vides det ikke hvorvidt de har en effektiv kvantealgoritme til at løse dem. Det er stadigt et åbent spørgsmål, men noget tyder på at det ikke er tilfældet. Med andre ord kan vi på nuværende tidspunkt effektivt løse visse NP-problemer, men ikke andre.
Desværre er der nogen som påstår at kvantecomputere får hele NP-hierarkiet til at kollapse - og det er ikke tilfældet. Kvantecomputere kan heller ikke søge som en nondeterministisk Turingmaskine - hvis det var tilfældet ville hierarkiet kollapse på samme vis.
Spørgsmål
Som jeg husker det, kan ethvert NP problem omskrives til et NP problem af en anden type i polynomiel tid, e.g. faktorisering til travelling salesman.
Så hvis man fik skovlen under bare et NP-problem, havde man i princippet løst dem alle.
Hvis jeg husker rigtigt, er illustrationen med mængderne vel forkert? - for så skal P og NP mængderne være disjunkte?
Re: Spørgsmål
Som jeg husker det, kan ethvert NP problem omskrives til et NP problem af en anden type i polynomiel tid, e.g. faktorisering til travelling salesman. Så hvis man fik skovlen under bare et NP-problem, havde man i princippet løst dem alle. Hvis jeg husker rigtigt, er illustrationen med mængderne vel forkert? - for så skal P og NP mængderne være disjunkte?
Du tænker på NP-komplette problemer, og i illustrationen er de også disjunkte mængder for antagelsen P/=NP.
Re: Kvante-computere og NP
Så til spørgsmålet. Kvantecomputere splitter NP-klassen. Der findes problemer i NP-klassen som lader sig effektivt løse med en kvantecomputer. Men der findes imidlertid også problemer hvor det ikke vides om en kvantecomputer giver en effektiv løsning.
Korrekt, men det er jo også et næsten trivielt udsagn. Funktionen der beregner om inddata er den tomme streng eller ej, er i NP, og den kan man godt få et kvantesystem til at beregne...
Primtalsfaktorisering, som nævnes i artiklen, kan effektivt løses på en kvantecomputer via Shors algoritme. Kvante-algoritmen giver en effektiv metode til at finde en (primtals-)faktor. Formelt ligger Shors algoritme i klassen BQP (Bounded-error Quantum Polynomial time).
Det bør nok nævnes udtrykkeligt at det ikke vides om heltalsfaktorisering er NP-komplet eller ej. Så selv om beviset for P!=NP skulle holde, er det ikke dermed vist at faktorisering ikke kan gøres hurtigt.
Kulturforskelle matematikere/de andre?
Den her tråd er helt sjov.
Hvorfor nu det?
Jo, for når man følger de teknologiske (og mere eller mindre politiske) diskussioner her på ingeniøren, er der altid nogle debattører, der klassificerer de andre som - nåja, ikke pænt.
Her: Sobert - tørt - fagligt!
Kommentarer (15)