Abstrakt. Under detta årtionde har det observerats att många verkliga grafer, som webben och några sociala och metaboliska nätverk, har en skalfri struktur. Dessa grafer kännetecknas av en stor variation i arititeten av noder, som verkar följa en makt-lag fördelning. Detta kom som en stor överraskning för forskare som var genomsyrade av traditionen med klassiska slumpmässiga nätverk. SAT-fall kan också ses som (bi-partit) diagram. I denna uppsats studerar vi många familjer av industriella SAT-fall som används i SAT-tävlingar, och visar att de flesta av dem också presenterar denna skala-fria struktur. Tvärtom, slumpmässiga SAT-fall, som ses som grafer, är närmare den klassiska slumpmässiga grafmodellen, där raritet av noder följer en Poisson-fördelning med liten variation. Detta skulle förklara deras särart. Vi analyserar också vad som händer när vi direktierar en bråkdel av variablerna, slumpmässigt eller med hjälp av vissa heuristiker, och hur den skalfria strukturen modifieras av dessa momentiationer. Slutligen studerar vi hur strukturen modifieras under genomförandet av en SAT-lösare och drar slutsatsen att den skalfria strukturen bevaras.
De flesta industriella SAT-fall har en skalfri struktur REF.
On the Structure of Industrial SAT Instances ⋆
{'venue': 'CP', 'journal': None, 'mag_field_of_study': ['Computer Science']}