All reports by Author Joseph Culberson:

__
TR04-012
| 19th December 2003
__

Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore#### The Resolution Complexity of Random Graph $k$-Colorability

Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore

We consider the resolution proof complexity of propositional formulas which encode random instances of graph $k$-colorability. We obtain a tradeoff between the graph density and the resolution proof complexity.

For random graphs with linearly many edges we obtain linear-exponential lower bounds on the length of resolution refutations. For any $\epsilon>0$, ...
more >>>