Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > DAVID MITCHELL:
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

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


TR01-074 | 12th October 2001
Joshua Buresh-Oppenheim, David Mitchell

Linear and Negative Resolution are Weaker than Resolution

Comments: 1

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




ISSN 1433-8092 | Imprint