Fasövergången i binära begränsningar tillfredsställelse problem, dvs. Övergången från en region där nästan alla problem har många lösningar till en region där nästan alla problem inte har några lösningar, eftersom begränsningarna blir hårdare, undersöks genom att man undersöker beteendet hos prover av slumpmässiga problem. Till skillnad från det teoretiska arbetet, som handlar om problemasymptotiskt beteende i takt med att antalet variabler blir större, handlar detta dokument om lokaliseringen av fasövergången i vissa problem. Noggrannheten hos en förutsägelse baserad på det förväntade antalet lösningar diskuteras; det visas att variationen i antalet lösningar kan användas för att sätta gränser vid fasövergången och för att indikera exaktheten i förutsägelsen. En klass av glesa problem, för vilka förutsägelsen är känd för att vara felaktig, beaktas i detalj; det visas att för dessa problem, fasövergången beror på topologin för begränsningskurvan samt på tätheten i begränsningarna.
I REF har det konstaterats att för problem med begränsad tillfredsställelse ökar svårigheten monotont genom att fasövergångsparametern minskas.
Locating the Phase Transition in Binary Constraint Satisfaction Problems
{'venue': 'Artificial Intelligence', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}