ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-074 | 12th October 2001 00:00

Linear and Negative Resolution are Weaker than Resolution

RSS-Feed




TR01-074
Authors: Joshua Buresh-Oppenheim, David Mitchell
Publication: 29th October 2001 22:10
Downloads: 382
Keywords: 


Abstract:

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 linear resolution.


Comment(s):

Comment #1 to TR01-074 | 10th December 2002 18:08





Comment #1
Authors: Joshua Buresh-Oppenheim
Accepted on: 10th December 2002 18:08
Downloads: 269
Keywords: 


Abstract:




ISSN 1433-8092 | Imprint