Dr Stefan Dantchev s.s.dantchev@durham.ac.uk
Assistant Professor
Planar tautologies hard for resolution
Dantchev, Stefan; Riis, Soren
Authors
Soren Riis
Abstract
We prove exponential lower bounds on the resolution proofs of some tautologies, based on rectangular grid graphs. More specifically, we show a 2/sup /spl Omega/(n)/ lower bound for any resolution proof of the mutilated chessboard problem on a 2n/spl times/2n chessboard as well as for the Tseitin tautology (G. Tseitin, 1968) based on the n/spl times/n rectangular grid graph. The former result answers a 35 year old conjecture by J. McCarthy (1964).
Citation
Dantchev, S., & Riis, S. (2001). Planar tautologies hard for resolution. In 42nd IEEE Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada ; proceedings (220-229). https://doi.org/10.1109/sfcs.2001.959896
Conference Name | 42nd IEEE Symposium of Foundations of Computer Science |
---|---|
Conference Location | Las Vegas, Nev |
Publication Date | 2001-10 |
Deposit Date | Feb 27, 2008 |
Publicly Available Date | Nov 1, 2010 |
Publisher | Institute of Electrical and Electronics Engineers |
Pages | 220-229 |
Book Title | 42nd IEEE Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada ; proceedings. |
DOI | https://doi.org/10.1109/sfcs.2001.959896 |
Files
Published Conference Proceeding
(233 Kb)
PDF
Copyright Statement
© 2001 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
You might also like
Combinatorial Axiomatisation of Edge-weighted PageRank
(2016)
Journal Article
Relativization makes contradictions harder for Resolution
(2013)
Journal Article
Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
(2012)
Journal Article
Cutting Planes and the Parameter Cutwidth
(2012)
Journal Article
Parameterized Proof Complexity
(2011)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search