Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > EXPONENTIAL TIME ALGORITHM:
Reports tagged with exponential time algorithm:
TR15-136 | 28th July 2015
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

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

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 ... more >>>

TR16-100 | 27th June 2016
Suguru Tamaki

#### A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates

We consider depth 2 unbounded fan-in circuits with symmetric and linear threshold gates. We present a deterministic algorithm that, given such a circuit with $n$ variables and $m$ gates, counts the number of satisfying assignments in time $2^{n-\Omega\left(\left(\frac{n}{\sqrt{m} \cdot \poly(\log n)}\right)^a\right)}$ for some constant $a>0$. Our algorithm runs in time ... more >>>

ISSN 1433-8092 | Imprint