Portal de Periódicos da CAPES

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

2015; Society for Industrial and Applied Mathematics; Volume: 22; Linguagem: Inglês

1433-8092

Takayuki Sakai, K. Seto, Suguru Tamaki, Junichi Teruyama,

Formal Methods in Verification

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.