Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

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: 3569
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: 1758
Keywords: 


Abstract:




ISSN 1433-8092 | Imprint