Computer Science – Discrete Mathematics
Scientific paper
2009-10-16
Computer Science
Discrete Mathematics
Scientific paper
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.
Nordström Jakob
Razborov Alexander
No associations
LandOfFree
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-124045