On the complexity of finding narrow proofs

Details On the complexity of finding narrow proofs On the complexity of finding narrow proofs

2012-04-03

arxiv.org/abs/1204.0775v1

Computer Science

Logic in Computer Science

Scientific paper

We study the complexity of the following "resolution width problem": Does a given 3-CNF have a resolution refutation of width k? We prove that the problem cannot be decided in time O(n^((k-3)/12)). This lower bound is unconditional and does not rely on any unproven complexity theoretic assumptions. The lower bound is matched by a trivial upper bound of n^O(k). We also prove that the resolution width problem is EXPTIME-complete (if k is part of the input). This confirms a conjecture by Vardi, who has first raised the question for the complexity of the resolution width problem. Furthermore, we prove that the variant of the resolution width problem for regular resolution is PSPACE-complete, confirming a conjecture by Urquhart.

Affiliated with

Also associated with

No associations

Rating

On the complexity of finding narrow proofs 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 the complexity of finding narrow proofs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the complexity of finding narrow proofs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-356191