The Complexity of Divide and Conquer
Dmitri Akatov
Info
|
Date |
24th November 2009 (week 7, Michaelmas Term 2009) |
|
Time |
11:30 |
|
Place |
478 |
Abstract
Hypergraph decompositions are a handy tool in database theory used to transform cyclic queries into acyclic structures, thus highly reducing the complexity of many problems, in particular that of the Boolean Conjunctive Query (BCQ) problem. In particular the BCQ problem for the class of queries with a bounded generalized hypertree width (GHW) are feasible in LOGCFL, a low and highly parallelizable complexity class.The trees associated with generalized hypertree decompositions generally do not possess any special structure and in the worst case have depth linear in the size of the hypergraph and a branching factor of 1. This, however, has negative effects on the parallelization of the BCQ problem. In fact, parallelization works best if a problem splits into smaller subproblems of approximately the same size, in the style of many well-known divide-and-conquer type algorithms. For hypergraph decompositions this corresponds to the underlying trees being approximately balanced.
We define a new type of decomposition, which possesses the above property, called a balanced cut decomposition. Investigating the exact complexity of the BCQ problem for the class of queries of bounded balanced cut width (BCW) leads to the definition of a new computational model: The Auxiliary Transparent Pushdown Automaton (AuxTPDA). This model is very similar to Auxiliary Pushdown Automata (AuxPDAs), with the exception that the stack now becomes transparent, i.e. can be read (but not popped or pushed) anywhere.
We show that the above problem is complete for the class of problems solvable by a nondeterministic AuxTPDA simultaneously bounded by polynomial time, logarithmic space and square-logarithmic usage of the stack. We show that checking whether a query has a Balanced Cut Decomposition of bounded width is feasible in this class, also. We also present deterministic algorithms for the above problems, and argue why they are highly parallelizable.
We finally relate this new class to existing complexity classes like LOGCFL and NTiSp(poly,log^2).
Further info
|
Related series |