文章基本信息

标题：Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs
本地全文：下载
作者：Atsuki Nagao ; Kazuhisa Seto ; Junichi Teruyama 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：92
页码：58:1-58:10
DOI：10.4230/LIPIcs.ISAAC.2017.58
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The satisfiability of a given branching program is to determine whether there exists a consistent path from the root to 1-sink. In a syntactic read-k-times branching program, each variable appears at most k times in any path from the root to a sink. We provide a satisfiability algorithm for syntactic read-k-times branching programs with n variables and m edges that runs in time O\left(\poly(n, m^{k^2})\cdot 2^{(1-\mu(k))n}\right), where \mu(k) = \frac{1}{4^{k+1}}. Our algorithm is based on the decomposition technique shown by Borodin, Razborov and Smolensky [Computational Complexity, 1993].
关键词：branching program; read-k-times; satisfiability; moderately exponential time; polynomial space