Vi studerar problem med begränsad tillfredsställelse på den så kallade planterade slumpmässiga ensemblen. Vi visar det för en viss klass av problem, t.ex. Graf färg, många av egenskaperna hos den vanliga slumpmässiga ensemblen är kvantitativt identiska i den planterade slumpmässiga ensemblen. Vi studerar strukturfasövergångar och det enkla/hårda/lätta mönstret i den genomsnittliga beräkningskomplexiteten. Vi diskuterar också det finita temperaturfasdiagrammet och finner en nära koppling till flytande/glas/solid fenomenologi. PACS nummer: 75.50.Lk,89.70.Eg,64.70.qd Problem med begränsad tillfredsställelse (CSPs) står på roten till teorin om beräkningskomplex [1] och uppstår inom datavetenskap, fysik, ingenjörsvetenskap och många andra vetenskapsområden. Betrakta en uppsättning av N diskreta variabler och en uppsättning M Booleska begränsningar; problemet består i att hitta en konfiguration av variabler som uppfyller alla begränsningar eller i att bevisa att ingen sådan konfiguration finns. Algoritmiska tillvägagångssätt för NP-kompletterade CSP [1] är en av de största utmaningarna i dagens vetenskap. Ensembler av slumpmässiga CSPs, där begränsningarna väljs enhetligt slumpmässigt från vissa föreskrivna distribution, används för att förstå den genomsnittliga beräkning komplexitet [2, 3]. Tekniker från statistisk fysik av glasiga system har gjort det möjligt för oss att sprida nytt ljus över problemet och om ursprunget till den genomsnittliga algoritmiska hårdheten [4, 5, 6]. En viktig punkt i utvärderingen av prestandan hos nya algoritmer för hårda CSPs är att kunna generera svåra fall som garanterat är tillfredsställande. Plantering är det mest standardiserade sättet att göra så: man väljer först en konfiguration av variabler och sedan endast tar hänsyn till begränsningar som är kompatibla med denna planterade konfiguration. Många plantering protokoll har införts [7, 8, 9] Men förståelsen av när och varför de ger en svår instans är fortfarande mycket dålig jämfört med vad som är känt för den rent slumpmässiga ensemble [4, 5, 6]. Detta beror på att planteringen av en lösning förändrar ensemblens egenskaper. Det förväntas dessutom ofta att den planterade lösningen är lättare att hitta än en slumpmässig, vilket faktiskt har bevisats för hög densitet av begränsningar [10, 11, 12]. Svåra fall med en känd lösning är också tilltalande för kryptografisk tillämpning eftersom de ger bra enkelriktade funktioner. Planterade fall kan också bero på tillämpningar där endast begränsningar som är förenliga med systemets ursprungliga tillstånd läggs till. I detta brev visar vi att för en specifik, men ändå stor, klass av CSPs, kan man enkelt generera planterade instanser genom att dölja en tyst lösning som inte har inflytande på de flesta av ensemblens egenskaper. Det kanoniska exemplet på en CSP där en lösning kan planteras på det tysta sättet är grafen q-färgning problem som vi ska illustrera våra fynd om fasdiagram och den genomsnittliga algoritmisk hårdhet. Den klass av problem som tillåter ett enkelt tyst gömställe kommer att diskuteras mot slutet av brevet. Gömma utan att ändra - Graf färg problemet består i att avgöra om N vertexes av en graf kan färgas med endast q färger på ett sådant sätt att var två intilliggande hörn har olika färger. Kontrollparametern är den genomsnittliga graden av variabler c, och vi anser att den termodynamiska gränsen N → ∞. I statistisk fysik motsvarar detta problem en Potts antiferromagnet [13, 14]. Sättet att plantera en tyst lösning i graf färg problemet är faktiskt den mest naturliga: Man tilldelar en slumpmässig färg med lika stor sannolikhet till var och en av N hörn, och sedan konstruerar grafen genom att slumpmässigt kasta länkar mellan hörn av olika färger. Med hjälp av hålighetsmetoden [15] beskriver vi fasdiagrammet och lösningarnas struktur i denna planterade ensemble. I den stora N-gränsen är gradfördelningen i de planterade graferna Poissonian med medel c, och därmed är de lokalt trädliknande precis som de vanliga slumpmässiga Erdös-Rényi-graferna. Efter hålighetsinflygningen [14, 15] kan trosutrotning (BP) ekvationer skrivas. Anteckna i→j är sannolikheten för att platsen i tar färg s i avsaknad av webbplatsen j: där Z i→j är en normalisering som säkerställer att entropin per plats s = S/N kan beräknas på så sätt om fördelningen P ( ska) över grafen är känd. Om man antar att det inte finns några korrelationer på lång sikt, kan rekursiva ekvationer på denna fördelning skrivas och lösas via populationsdynamikstekniken [15]. I den planterade ensemblen måste man skilja mellan de platser som planterades med olika
Det är bara på de faktoriserade problemen där det finns ett mycket nära samband mellan den vanliga slumpmässiga och planterade ensemblen, som diskuteras i REF.
Hiding Quiet Solutions in Random Constraint Satisfaction Problems
{'venue': 'Phys. Rev. Lett. 102, 238701 (2009)', 'journal': None, 'mag_field_of_study': ['Physics', 'Computer Science', 'Medicine']}