Detta papper utvecklar övre och nedre gränser för sannolikheten för Booleska funktioner genom att behandla flera förekomster av variabler som oberoende och tilldela dem nya individuella sannolikheter. Vi kallar detta tillvägagångssätt dissociation och ger en exakt karakterisering av optimala omedvetna gränser, d.v.s. När de nya sannolikheterna väljs oberoende av sannolikheten för alla andra variabler. Vår motivation kommer från den viktade modellen räkna problem (eller, motsvarande, problemet med att beräkna sannolikheten för en Boolesk funktion), som är #P-hård i allmänhet. Genom att utföra flera dissociationer, kan man omvandla en Boolesk formel vars sannolikhet är svår att beräkna, till en vars sannolikhet är lätt att beräkna, och som garanterat ger en övre eller nedre gräns för sannolikheten för den ursprungliga formeln genom att välja lämpliga sannolikheter för de dissocierade variablerna. Våra nya gränser kastar ljus över kopplingen mellan tidigare avkopplingsbaserade och modellbaserade approximationer och förenar dem som konkreta val i ett större designutrymme. Vi visar också hur vår teori tillåter en standard relational database management system (DBMS) till både övre och nedre bundet hårda probabilistiska frågor i garanterad polynom tid.
Teoretiska övre och nedre gränser för dissociation av Booleska formler, inklusive Theorem 8, visades i REF.
Oblivious Bounds on the Probability of Boolean Functions
{'venue': 'Pre-print for ACM Transactions on Database Systems, January 2014, Vol 39, No 1, Article 5', 'journal': None, 'mag_field_of_study': ['Computer Science']}