کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4661728 1633458 2014 55 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Short propositional refutations for dense random 3CNF formulas
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Short propositional refutations for dense random 3CNF formulas
چکیده انگلیسی
The idea is based on demonstrating efficient propositional correctness proofs of the random 3CNF unsatisfiability witnesses given by Feige, Kim and Ofek [23]. 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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 165, Issue 12, December 2014, Pages 1864-1918
نویسندگان
, ,