Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-136 | 28th July 2015 15:20

A Satisfiability Algorithm for Depth-2 Circuits with a Symmetric Gate at the Top and AND Gates at the Bottom

RSS-Feed

Abstract:

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) \cdot 2^{n-n^{1/O(t)}}$ for instances with $n$ variables and $O(n^t)$ clauses.



ISSN 1433-8092 | Imprint