| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution | Jakob Nordström
; Alexander Razborov
; | Date: |
16 Oct 2009 | Abstract: | In the context of proving lower bounds on proof space in k-DNF resolution,
[Ben-Sasson and Nordstrom 2009] introduced the concept of minimally
unsatisfiable sets of k-DNF formulas and proved that a minimally unsatisfiable
k-DNF set with m formulas can have at most O((mk)^(k+1)) variables. They also
gave an example of such sets with Omega(mk^2) variables.
In this paper we significantly improve the lower bound to Omega(m)^k, which
almost matches the upper bound above. Furthermore, we show that this implies
that the analysis of their technique 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
Nordstrom 2009] should hold, a fundamentally different approach would be needed
to obtain such results. | Source: | arXiv, 0910.3127 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |