Under the auspices of the Computational Complexity Foundation (CCF)

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

TR15-136
Authors: Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama
Publication: 21st August 2015 14:50
$\poly(n^t) \cdot 2^{n-n^{1/O(t)}}$ for instances with $n$ variables and $O(n^t)$ clauses.