Počet záznamů: 1
Tighter Hard Instances for PPSZ
- 1.
SYSNO ASEP 0476174 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název Tighter Hard Instances for PPSZ Tvůrce(i) Pudlák, Pavel (MU-W) RID, SAI
Scheder, D. (CN)
Talebanfard, Navid (MU-W) SAI, ORCID, RIDČíslo článku 85 Zdroj.dok. 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). - Dagstuhl : Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2017 / Chatzigiannakis I. ; Indyk P. ; Kuhn F. ; Muscholl A. - ISSN 1868-8969 - ISBN 978-3-95977-041-5 Rozsah stran s. 1-13 Poč.str. 13 s. Forma vydání Online - E Akce 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) Datum konání 10.07.2017 - 14.07.2017 Místo konání Warsaw Země PL - Polsko Typ akce WRD Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova k-SAT ; strong exponential time hypothesis ; PPSZ ; resolution Vědní obor RIV BA - Obecná matematika Obor OECD Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) CEP GBP202/12/G061 GA ČR - Grantová agentura ČR Institucionální podpora MU-W - RVO:67985840 EID SCOPUS 85027256429 DOI 10.4230/LIPIcs.ICALP.2017.85 Anotace We construct uniquely satisfiable k-CNF formulas that are hard for the PPSZ algorithm, the currently best known algorithm solving k-SAT. This algorithm tries to generate a satisfying assignment by picking a random variable at a time and attempting to derive its value using some inference heuristic and otherwise assigning a random value. The weak PPSZ checks all subformulas of a given size to derive a value and the strong PPSZ runs resolution with width bounded by some given function. Firstly, we construct graph-instances on which weak PPSZ has savings of at most (2 + epsilon)/k: the saving of an algorithm on an input formula with n variables is the largest gamma such that the algorithm succeeds (i.e. finds a satisfying assignment) with probability at least 2^{- (1 - gamma) n}. Since PPSZ (both weak and strong) is known to have savings of at least (pi^2 + o(1))/6k, this is optimal up to the constant factor. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2018
Počet záznamů: 1