Portal de Periódicos da CAPES

Search rearrangement backtracking and polynomial average time

1983; Elsevier BV; Volume: 21; Issue: 1-2 Linguagem: Inglês

10.1016/s0004-3702(83)80007-1

1872-7921

Paul W. Purdom,

semigroups and automata theory

The average time required for simple search rearrangement backtracking is compared with that for ordinary backtracking when each algorithm is used to find all solutions for random conjunctive normal form predicates. The sets of random predicates are characterized by v: the number of variables, t(v): the number of clauses, and p(v): the probability that a literal appears in clause. For large v if vp(v) 1n 2, there is a difficult region where the average number of solutions per problem is exponentially small, but backtracking requires an exponentially large time. The difficult region for search rearrangement backtracking is only slightly smaller than the difficult region for ordinary backtracking. It is conjectured that search rearrangement backtracking is exponentially faster than ordinary backtracking for nearly all of the difficult region. It is proved that there is no major advantage in using search rearrangement backtracking outside of the difficult region.