A method to calculate the average size of Davis-Putnam-Loveland-Logemann (DPLL) search trees for random computational problems is introduced, and applied to the satisfiability of random CNF formulas (SAT) and the coloring of random graph (COL) problems. We
5
2
n
Ju
6
1
]
C
C
.
s
c
[
1
v
9
6
6
5
/0
sc
:viXr
aAgeneratingfunctionmethodfortheaverage-caseanalysisofDPLLR´emiMonassonCNRS-LaboratoiredePhysiqueTh´eorique,ENS,Paris,Francemonasson@lpt.ens.frAbstract.AmethodtocalculatetheaveragesizeofDavis-Putnam-Loveland-Logemann(DPLL)searchtreesforrandomcomputationalprob-lemsisintroduced,andappliedtothesatis abilityofrandomCNFfor-mulas(SAT)andthecoloringofrandomgraph(COL)problems.Weestablishrecursionrelationsforthegeneratingfunctionsoftheaveragenumbersof(variableorcolor)assignmentsatagivenheightinthesearchtree,whichallowustoderivetheasymptoticsoftheexpectedDPLLtreesize,2Nω+o(N),whereNistheinstancesize.ωiscalculatedasafunc-tionoftheinputdistributionparameters(ratioofclausespervariableforSAT,averagevertexdegreeforCOL),andthebranchingheuristics.1Introductionandmainresults.Manye ortshavebeendevotedtothestudyoftheperformancesoftheDavis-Putnam-Loveland-Logemann(DPLL)procedureandmoregenerally,res-olutionproofcomplexityforcombinatorialproblemswithrandomlygeneratedinstances.Twoexamplesarerandomk-Satis ability(k-SAT),whereaninstancebuiltFisafromuniformlyNBooleanandrandomlyvariableschosenandtheirsetnegationsofM=α(withNdisjunctionsnorepetitionofkandliteralsnocomplementaryliterals),andrandomgraphk-Coloring(k-COL),whereanin-stanceFisanErd os-R´enyirandomgraphfromG(N,p=c/N)i.e.withaveragevertexdegreec.
Originally,e ortswereconcentratedontherandomwidthdistributionfork-SAT,whereeachliteralappearwitha xedprobability.Franco,Purdomandcollaboratorsshowedthatsimpli edversionsofDPLLhadpolynomialaverage-casecomplexityinthiscase,seeforreviews.Itwasthenrecognizedthatthe xedclauselengthensemblemightprovideharderinstancesforDPLLChv´atalandSzemer´ediindeedshowedthatDPLLproofsizeisw.h.p.exponen-tiallylarge(inNat xedratioα)foranunsatis ableinstanceLateron,Beameetal.showedthattheproofsizewasw.h.p.boundedfromaboveby
The average case analysi... 暂无评价 97页 免费 Average-case analysis of... 暂无评价 8页 免费 A generating function me... 暂无评价 14页 免费 Analysis...
The average case analysi... 暂无评价 97页 免费 Average-case analysis of... 暂无评价 8页 免费 A generating function me... 暂无评价 14页 免费 Analysis...
热门文档