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

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

2005-06-16

arxiv.org/abs/cs/0506069v1

RANDOM 2005, Berkeley, CA, \'Etats-Unis d'Am\'erique, p.402-413

Computer Science

Computational Complexity

RANDOM 2005, Berkeley, August 22-24

Scientific paper

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 establish recursion relations for the generating functions of the average numbers of (variable or color) assignments at a given height in the search tree, which allow us to derive the asymptotics of the expected DPLL tree size, 2^{N w + o(N)}, where N is the instance size. w is calculated as a function of the input distribution parameters (ratio of clauses per variable for SAT, average vertex degree for COL), and the branching heuristics.

Affiliated with

Also associated with

No associations

Rating

A generating function method for the average-case analysis of DPLL does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A generating function method for the average-case analysis of DPLL, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A generating function method for the average-case analysis of DPLL will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-4874