A Satisfiability Algorithm for Depth-2 Circuits with a Symmetric Gate at the Top and AND Gates at the Bottom.
Takayuki Sakai, K. Seto, Suguru Tamaki, Junichi Teruyama · Electronic colloquium on computational complexity · 2015
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) · 2n−n1/O(t) for instances with n variables and O(n) clauses.