Med tanke på en Boolesk formel, problemet med modellräkning, även kallad #SAT är att beräkna antalet lösningar av  och. Modellräkning är ett grundläggande problem inom artificiell intelligens med ett brett spektrum av tillämpningar inklusive probabilistiska resonemang, beslutsfattande under osäkerhet, kvantifierat informationsflöde, och liknande. Motiverad av framgången för SAT-lösare, har det funnits ett ökat intresse för utformningen av hashing-baserade tekniker för ungefärlig modell räkna för det senaste årtiondet. Vi profilerade den toppmoderna ungefärliga modellräknaren CaMC2 och noterade att över 99.99% av tiden konsumeras av den underliggande SAT-lösaren, CryptoMiniSat. Denna observation motiverade oss att fråga: Kan vi utforma en effektiv underliggande CNF-XOR SAT-lösare som kan dra nytta av strukturen av hashing-baserade algoritmer och skulle detta leda till en effektiv ungefärlig modellräknare? Det viktigaste bidraget i detta dokument är ett jakande svar på ovanstående fråga. Vi presenterar en ny arkitektur, BIRD, för att hantera CNF-XOR-formler som uppstår från hashingbaserade tekniker. Den resulterande hashing-baserade ungefärliga modellräknaren, kallad CaMC3, använder BIRD-ramverket i sin underliggande SAT-lösare, CryptoMinisat. Såvitt vi vet genomförde vi den mest omfattande studien av utvärderingsprestanda för beräkningsalgoritmer som omfattade 1896 riktmärken med beräkningssats på sammanlagt 86400 beräkningstimmar. Vår experimentella utvärdering visar på betydande prestandaförbättringar i drifttid för CaMC3 jämfört med CaMC2. I synnerhet löser vi 648 riktmärken mer än CaMC2, den senaste ungefärliga modellräknaren och för alla formler där både CaMC2 och CaMC3 inte tog timeout och tog mer än 1 sekunder, är medelhastigheten 284,40 -mer än två storleksordningar.
REF har också använts för att beräkna exakta modellräkningar.
BIRD: Engineering an Efficient CNF-XOR SAT Solver and Its Applications to Approximate Model Counting.
{'venue': 'AAAI', 'journal': None, 'mag_field_of_study': ['Computer Science']}