Number of the records: 1
Random resolution refutations
- 1.
SYSNO ASEP 0477098 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title Random resolution refutations Author(s) Pudlák, Pavel (MU-W) RID, SAI
Thapen, Neil (MU-W) RID, SAIArticle number 1 Source Title 32nd Computational Complexity Conference (CCC 2017). - Dagstuhl : Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2017 / O’Donnell R. - ISSN 1868-8969 - ISBN 978-3-95977-040-8 Pages s. 1-10 Number of pages 10 s. Publication form Online - E Action 32nd Computational Complexity Conference (CCC 2017) Event date 06.07.2017 - 09.07.2017 VEvent location Riga Country LT - Lithuania Event type WRD Language eng - English Country DE - Germany Keywords proof complexity ; random ; resolution ; resolution Subject RIV BA - General Mathematics OECD category Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) Institutional support MU-W - RVO:67985840 EID SCOPUS 85028743827 DOI 10.4230/LIPIcs.CCC.2017.1 Annotation We study the random resolution refutation system definedin [Buss et al. 2014]. This attempts to capture the notion of a resolution refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the other hand, if P does not equal NP, then random resolution cannot be polynomially simulated by any proof system in which correctness of proofs is checkable in polynomial time. We prove several upper and lower bounds on the width and size of random resolution refutations of explicit and random unsatisfiable CNF formulas. Our main result is a separation between polylogarithmic width random resolution and quasipolynomial size resolution, which solves the problem stated in [Buss et al. 2014]. We also prove exponential size lower bounds on random resolution refutations of the pigeonhole principle CNFs, and of a family of CNFs which have polynomial size refutations in constant depth Frege. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2018
Number of the records: 1