Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Marked Items 
Alerts
Order History
Saved Items
All
Favorites
    
Book Chapter Printable view
Width Versus Size in Resolution Proofs

Width Versus Size in Resolution Proofs

Book SeriesLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
ISSN0302-9743 (Print) 1611-3349 (Online)
VolumeVolume 3959/2006
BookTheory and Applications of Models of Computation
DOI10.1007/11750321
Copyright2006
ISBN978-3-540-34021-8
CategoryPlenary Lectures
DOI10.1007/11750321_6
Pages79-88
Subject CollectionComputer Science
SpringerLink DateFriday, May 05, 2006
Add to marked items

Plenary Lectures

Width Versus Size in Resolution Proofs

Alasdair Urquhart1 Contact Information

(1)  Departments of Philosophy and Computer Science, University of Toronto, Toronto, Ontario M5S 1A1, Canada
Abstract
The complexity of resolution refutations of contradictory sets of clauses in propositional logic has been investigated deeply over the last forty years, beginning with the groundbreaking paper of Tseitin [16], based on a talk given in a Leningrad seminar of 1966.
A general theme that emerged gradually in the course of the intensive investigations of the last few decades has been that of basing size lower bounds on lower bounds on the width of refutations. Roughly speaking, it turns out that in many cases, the minimum size of a refutation is exponential in the minimum width.

Contact Information Alasdair Urquhart
Email: urquhart@cs.toronto.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext
more options
Find


Export this chapter
Export this chapter as RIS | Text
 
Frequently asked questions | General information on journals and books | Send us your feedback | Impressum | Contact
© Springer. Part of Springer Science+Business Media
Privacy, Disclaimer, Terms and Conditions, © Copyright Information
Remote Address: 38.107.191.111 • Server: mpweb16
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)