文章基本信息
- 标题：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
