Vi bestämmer den exakta fryströskel, r f, för en familj av modeller av slumpmässiga booleska begränsningar tillfredsställelse problem, inklusive NAE-SAT och hypergraph 2-färg, när begränsningen storlek är tillräckligt stor. Om begränsning-densitet av en slumpmässig CSP, F, i vår familj är större än r f sedan för nästan varje lösning av F, ett linjärt antal variabler fryses, vilket innebär att deras färger inte kan ändras genom en sekvens av förändringar där vi ändrar o(n) variabler i taget, alltid byta till en annan lösning. Om begränsningen-densitet är mindre än r f, sedan nästan varje lösning har o(n) frysta variabler.
REF studerade ett brett spektrum av problem med booleska begränsningar, inklusive hypergraf 2-färgning.
Frozen variables in random boolean constraint satisfaction problems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}