ECCC-Report TR15-136https://eccc.weizmann.ac.il/report/2015/136Comments and Revisions published for TR15-136en-usFri, 21 Aug 2015 14:50:44 +0300
Paper TR15-136
| 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,
Junichi Teruyama
https://eccc.weizmann.ac.il/report/2015/136In 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) \cdot 2^{n-n^{1/O(t)}}$ for instances with $n$ variables and $O(n^t)$ clauses.Fri, 21 Aug 2015 14:50:44 +0300https://eccc.weizmann.ac.il/report/2015/136