A Satisfiability Algorithm for Some Class of Dense Depth Two Threshold Circuits

Kazuyuki AMANO  Atsushi SAITO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.1   pp.108-118
Publication Date: 2015/01/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014EDP7127
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
satisfiability,  exact algorithm,  threshold circuit,  

Full Text: PDF>>
Buy this Article




Summary: 
Recently, Impagliazzo et al. constructed a nontrivial algorithm for the satisfiability problem for sparse threshold circuits of depth two which is a class of circuits with cn wires. We construct a nontrivial algorithm for a larger class of circuits. Two gates in the bottom level of depth two threshold circuits are dependent, if the output of the one is always greater than or equal to the output of the other one. We give a nontrivial circuit satisfiability algorithm for a class of circuits which may not be sparse in gates with dependency. One of our motivations is to consider the relationship between the various circuit classes and the complexity of the corresponding circuit satisfiability problem of these classes. Another background is proving strong lower bounds for TC0 circuits, exploiting the connection which is initiated by Ryan Williams between circuit satisfiability algorithms and lower bounds.