Short Propositional Refutations for Dense Random 3CNF Formulas

Details Short Propositional Refutations for Dense Random 3CNF Formulas Short Propositional Refutations for Dense Random 3CNF Formulas

2011-01-20

arxiv.org/abs/1101.3970v2

Computer Science

Computational Complexity

62 pages; improved introduction and abstract, and a changed title. Fixed some typos

Scientific paper

Random 3CNF formulas constitute an important distribution for measuring the average-case behavior of propositional proof systems. Lower bounds for random 3CNF refutations in many propositional proof systems are known. Most notably are the exponential-size resolution refutation lower bounds for random 3CNF formulas with $\Omega(n^{1.5-\epsilon}) $ clauses [Chvatal and Szemeredi (1988), Ben-Sasson and Wigderson (2001)]. On the other hand, the only known non-trivial upper bound on the size of random 3CNF refutations in a non-abstract propositional proof system is for resolution with $\Omega(n^{2}/\log n) $ clauses, shown by Beame et al. (2002). In this paper we show that already standard propositional proof systems, within the hierarchy of Frege proofs, admit short refutations for random 3CNF formulas, for sufficiently large clause-to-variable ratio. Specifically, we demonstrate polynomial-size propositional refutations whose lines are $TC^0$ formulas (i.e., $TC^0$-Frege proofs) for random 3CNF formulas with $ n $ variables and $ \Omega(n^{1.4}) $ clauses. The idea is based on demonstrating efficient propositional correctness proofs of the random 3CNF unsatisfiability witnesses given by Feige, Kim and Ofek (2006). Since the soundness of these witnesses is verified using spectral techniques, we develop an appropriate way to reason about eigenvectors in propositional systems. To carry out the full argument we work inside weak formal systems of arithmetic and use a general translation scheme to propositional proofs.

Affiliated with

Also associated with

No associations

Rating

Short Propositional Refutations for Dense Random 3CNF Formulas 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 Short Propositional Refutations for Dense Random 3CNF Formulas, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Short Propositional Refutations for Dense Random 3CNF Formulas will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-334358