All reports by Author David Mitchell:

__
TR04-012
| 19th December 2003
__

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

__
TR01-074
| 12th October 2001
__

Joshua Buresh-Oppenheim, David Mitchell#### Linear and Negative Resolution are Weaker than Resolution

Comments: 1

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 >>>

Joshua Buresh-Oppenheim, David Mitchell

We prove exponential separations between the sizes of

particular refutations in negative, respectively linear, resolution and

general resolution. Only a superpolynomial separation between negative

and general resolution was previously known. Our examples show that there

is no strong relationship between the size and width of refutations in

negative and ...
more >>>