Ett stort problem vid utvärdering av stokastiska lokala sökalgoritmer för NP-kompletta problem är behovet av en systematisk generation av hårda testfall med tidigare kända egenskaper hos de optimala lösningarna. På grundval av statistiska mekanik resultat föreslår vi slumpmässiga generatorer av hårda och tillfredsställande fall för 3-tillfredsställande problem (3-SAT). Utformningen av de svåraste problematikerna bygger på existensen av en första ordning ferromagnetisk fasövergång och den glasiga naturen av upphetsade tillstånd. De analytiska förutsägelserna bekräftas av numeriska resultat som erhållits från såväl kompletta som stokastiska lokala algoritmer. PACS nummer: 89.20.Ff, 02.60.Pn, 05.70.Fh, 75.10.Nr Inom naturvetenskap och artificiella system finns det många problem vars lösning kräver beräkningsresurser som växer exponentiellt med antalet variabler N som behövs för deras kodning. Konkreta exempel är optimering och kryptografiska problem inom datavetenskap, glasiga system och slumpmässiga strukturer inom fysik och kemi, slumpmässiga grafer i matematik och schemaläggningsproblem i verkliga tillämpningar. Att ha snabba och kraftfulla algoritmer för att lösa dessa problem är av primär betydelse för deras teoretiska studie såväl som för tillämpningar. Utvärderingen av sådana algoritmer baseras på tillgängligheten av hårda riktmärken med följande egenskaper: De ger problemfall, med en given känd lösning, på ett snabbt sätt (t.ex. linjär i N ), men upplösningen av en instans tar en tid exponentiellt i N för någon känd algoritm. Så de bästa algoritmerna kan enkelt väljas. I denna bokstav föreslår vi en ny generator av hårda och lösliga testfall, med alla de egenskaper som anges ovan. Det är baserat på ett NP-komplett problem [1] -nämligen 3-tillfredsställande (3-SAT). Huvudidén för konstruktion av sådana svåra och lösliga problem är mycket enkel: att dölja en känd lösning inom en mängd samexisterande slumpmässiga metastabila konfigurationer som utgör dynamiska barriärer. I det fysiska tillvägagångssättet baserat på en kartläggning från 3-SAT till en spinnglas modell [2], sådana slumpmässiga konfigurationer motsvarar glasiga tillstånd [3]. Det bör dock noteras att många tidigare försök att genomföra denna idé misslyckades, eftersom den slumpmässiga strukturen vanligtvis var lätt att ta bort, eller kunskap om att en lösning har tvingats kan utnyttjas för att hitta den. I de fall som vi föreslår ändrar inte förekomsten av en känd lösning strukturen i det glasiga tillståndet, vilket förvirrar lösaren och gör problemet svårt. Som en viktig tillämpning av dessa idéer på kryptografi [4] tillhandahålls slumpmässiga enkelriktade funktioner: Ett givet meddelande, t.ex. ett lösenord, kan kodas i en 3-SAT formel och därmed verifieras effektivt, men avkodning är extremt tidskrävande. Vi använder ramen för den typiska-fall computational komplexitet [5, 6]. Där har studien av slumpmässiga 3-SAT-problem spelat en viktig roll. En slumpmässig 3-SAT formel F består av M logiska klausuler {C μ } μ=1,...,M över en uppsättning N Booleska variabler {x i = 0, 1} i=1,...,N, med 0=FALSE och 1=TRUE. Varje klausul består av tre slumpmässigt utvalda booleska variabler som är sammankopplade med logiska or-operationer och som verkar negerade med sannolikhet 1/2, t.ex. C μ = (x i) x j) x k ). I F är klausulerna sammankopplade med logiska AND-operationer, F = M μ=1 C μ, så att alla klausuler måste uppfyllas samtidigt för att uppfylla formeln. En tillfredsställande logisk tilldelning av x i kallas också en lösning av F. Den slumpmässiga 3-SAT-modellen befanns genomgå en SAT/UNSAT-fasövergång [7] vid ett kritiskt förhållande α c = M/N  på 4,25 (N  på 1): Nedan α c, nästan alla formler är satisfiable, medan bortom nästan alla formler inte visar någon lösning. Vid denna tröskel, en stark exponentiell topp i den typiska (median) kostnaden för att hitta lösningar av de mest kända algoritmer visas. Problemaspekt som genereras nära den bildar en naturlig testbädd för optimering av heuristiska sökalgoritmer. Tillfredsställande och otillfredsställande fall existerar dock samtidigt i denna region. Många algoritmer av praktiskt intresse [8] är baserade på ofullständiga stokastiska lokala sökprocedurer, t.ex. simulerad glödgning [9] och walk-SAT algoritm [10]. Dessa algoritmer slutar när de har hittat en lösning, men de har inget sätt att reda ut, i polynom tid i N, Om en formel är otillfredsställande eller bara svårt att lösa. Det är därför mycket viktigt att generera riktmärken som är tillfredsställande och för vilka det algoritmiska beviset på denna tillfredsställelse tar en exponentiell tid i N. I denna skrivelse föreslår vi enkla och snabba generatorer av sådana referensproblem. De viktigaste idéerna är inspirerade av fysiska krav, och utnyttja den förmodade hård-
Ett annat tillvägagångssätt, som är ganska lätt att genomföra, har också föreslagits av REF: varje 3-SAT instans tvingas att vara tillfredsställande genom att förbjuda de klausuler som överträtts av både ett uppdrag och dess komplement.
Hiding solutions in random satisfiability problems: A statistical mechanics approach
{'venue': 'Phys. Rev. Lett. 88, 188701 (2002)', 'journal': None, 'mag_field_of_study': ['Medicine', 'Physics', 'Computer Science']}