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



REPORTS > KEYWORD > PROJECTIVE PLANES:
Reports tagged with Projective Planes:
TR97-007 | 21st February 1997
Stasys Jukna

Exponential Lower Bounds for Semantic Resolution

In a semantic resolution proof we operate with clauses only but allow {\em arbitrary} rules of inference: C_1 C_2 ... C_m __________________ C Consistency is the only requirement. We prove a very simple exponential lower bound for the size of bounded fanin semantic resolution proofs of a general {\em Hitting ... more >>>



ISSN 1433-8092 | Imprint