A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits

We give a nontrivial algorithm for the satisfiability problem for threshold circuits of depth two with a linear number of wires which improves over exhaustive search by an exponential factor. The independently interesting problem of the feasibility of sparse 0-1 integer linear programs is a special case. To our knowledge, our algorithm is the first to achieve constant savings even for the special case of Integer Linear Programming. The key idea is to reduce the satisfiability problem to the Vector Domination problem, the problem of checking whether there are two vectors in a given collection of vectors such that one dominates the other component-wise. Our result generalizes to formulas of arbitrary constant depth. We also provide a satisfiability algorithm with constant savings for depth two circuits with symmetric gates where the total weighted fan-in is at most linear in the number of variables. One of our motivations is proving strong lower bounds for TC0 circuits, exploiting the connection (established by Williams) between satisfiability algorithms and lower bounds. Our second motivation is to explore the connection between the expressive power of the circuits and the complexity of the corresponding circuit satisfiability problem.

Authors

• Russell Impagliazzo
• Ramamohan Paturi
• Stefan Schneider 0003

Keywords

• Logic gates
• Vectors
• Wires
• Polynomials
• Testing
• Integrated circuit modeling
• Complexity theory
• Lower Bound
• Savings
• Exhaustive Search
• Constant Depth
• Number Of Wires
• Number Of Values
• System Of Equations
• Game Theory
• Algorithm Design
• Sum Of Weights
• Zero-sum
• Circuit Design
• Linear Inequalities
• System Of Linear Equations
• Mixed Strategy
• Linear Size
• Convex Combination
• Output Gate
• Boolean Variable
• Pure Strategy
• Top Gate
• OR Gate
• Threshold Circuits
• Satisfiability Algorithms