文章基本信息

标题：PPSZ on CSP Instances with Multiple Solutions
本地全文：下载
作者：Dominik Scheder
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2018
卷号：2018
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：
We study the success probability of the PPSZ algorithm on ( d k ) -CSP formulas. We greatly simplify the analysis of Hertli, Hurbain, Millius, Moser, Szedlak, and myself for the notoriously difficult case that the input formula has more than one satisfying assignment.
关键词：Exact complexity ; NP-complete problems ; randomized algorithm