Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BINARY ENCODINGS:
Reports tagged with Binary Encodings:
TR18-165 | 20th September 2018
Stefan Dantchev, Nicola Galesi, Barnaby Martin

#### Resolution and the binary encoding of combinatorial principles

We investigate the size complexity of proofs in $RES(s)$ -- an extension of Resolution working on $s$-DNFs instead of clauses -- for families of contradictions given in the {\em unusual binary} encoding. A motivation of our work is size lower bounds of refutations in Resolution for families of contradictions in ... more >>>

ISSN 1433-8092 | Imprint