文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > A generating function method for the average-case analysis of DPLL
侵权投诉

A generating function method for the average-case analysis of DPLL

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

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email