کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4661728 | 1633458 | 2014 | 55 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Short propositional refutations for dense random 3CNF formulas
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
منطق ریاضی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
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
Journal: Annals of Pure and Applied Logic - Volume 165, Issue 12, December 2014, Pages 1864-1918
نویسندگان
Sebastian Müller, Iddo Tzameret,