文章基本信息

标题：A Satisfiability Algorithm for Depth-2 Circuits with a Symmetric Gate at the Top and AND Gates at the Bottom
本地全文：下载
作者：Takayuki Sakai ; Kazuhisa Seto ; Suguru Tamaki 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2015
卷号：2015
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：
In this paper, we present a moderately exponential time algorithm for the circuit satisfiability problem of depth-2 unbounded-fan-in circuits with an arbitrary symmetric gate at the top and AND gates at the bottom. As a special case, we obtain an algorithm for the maximum satisfiability problem that runs in time \poly ( n t ) 2 n − n 1 O ( t ) for instances with n variables and O ( n t ) clauses.
关键词：Circuit Satisfiability ; exponential time algorithm ; Maximum Satisfiability