Some algorithmic and complexity results for monotone Boolean duality (hypergraph transversal).
Published: 2004
Language: eng
Number of pages: 61
Description: Let   y  be a monotone CNF formula and let   4  be a monotone DNF formula. The problem of determining in polynomial time in the size of   y  and   4  whether   y&uharr;a=4&uharr; a  for all assignments alpha (known as DUAL) has been a longstanding open problem.We show that two popular families of algorithms for DUAL (Berge's  Sequential Method and Fredman and Khachiyan's Algorithm A ) are really restrictions of the DPLL class of algorithms which has long been studied in relation to SAT. We also present super-polynomial lower bounds for DPLL on two classes of read-once formulae. Finally, we present DPLLCache, DPLL with memorization, and show that DPLLCache is strictly stronger than DPLL and therefore also the Sequential Method and Algorithm A. In fact, we show that  DPLLCache can solve all read-once formulae using polynomial size decision trees.
Notes: Adviser: Toniann Pitassi.

Thesis (M.Sc.)--University of Toronto, 2004.

Electronic version licensed for access by U. of T. users.

Source: Masters Abstracts International, Volume: 42-06, page: 2231.

MICR copy on microfiche (1 microfiche).