Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-2700-4285
2011 (English)In: Automata, Languages and Programming 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, Springer Berlin/Heidelberg, 2011, 642-653 p.Conference paper, Published paper (Refereed)
Abstract [en]

A well-known theorem by Tarsi states that a minimally unsatisfiable CNF formula with m clauses can have at most m - 1 variables, and this bound is exact. In the context of proving lower bounds on proof space in k-DNF resolution, [Ben-Sasson and Nordström 2009] extended the concept of minimal unsatisfiability to sets of k-DNF formulas and proved that a minimally unsatisfiable k-DNF set with m formulas can have at most (mk) k + 1 variables. This result is far from tight, however, since they could only present explicit constructions of minimally unsatisfiable sets with Ω(mk 2) variables. In the current paper, we revisit this combinatorial problem and significantly improve the lower bound to (Ω(m)) k , which almost matches the upper bound above. Furthermore, using similar ideas we show that the analysis of the technique in [Ben-Sasson and Nordström 2009] for proving time-space separations and trade-offs for k-DNF resolution is almost tight. This means that although it is possible, or even plausible, that stronger results than in [Ben-Sasson and Nordström 2009] should hold, a fundamentally different approach would be needed to obtain such results.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2011. 642-653 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6755
Keyword [en]
CNF formulas, Combinatorial problem, Explicit constructions, Lower bounds, Time-space, Upper Bound
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-63103DOI: 10.1007/978-3-642-22006-7_54ISI: 000353447800054Scopus ID: 2-s2.0-79959927201ISBN: 978-364222005-0 (print)OAI: oai:DiVA.org:kth-63103DiVA: diva2:481632
Conference
38th International Colloquium on Automata, Languages and Programming, ICALP 2011, Zurich, 4 July 2011 through 8 July 2011
Note

QC 20120124

Available from: 2012-01-21 Created: 2012-01-21 Last updated: 2015-12-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Nordström, Jakob

Search in DiVA

By author/editor
Nordström, Jakob
By organisation
Theoretical Computer Science, TCS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 46 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf