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 \textrm{poly}(\log n)}\right) ^a\right) }\) for some constant \(a>0\) . Our algorithm runs in time super-polynomially faster than \(2^n\) if \(m=O(n^2/\log ^b n)\) for some constant \(b>0\) . Previously, such algorithms were only known for bounded depth circuits with linear threshold gates and a slightly super-linear number of wires [Impagliazzo-Paturi-Schneider, FOCS 2013 and Chen-Santhanam-Srinivasan, CCC 2016]. We also show that depth 2 circuits with \(O(n^2/\log ^b n)\) symmetric and linear threshold gates in total cannot compute an explicit function computable by a deterministic \(2^{O(n)}\) -time Turing machine with an NP oracle. Previously, even slightly super-linear lower bounds on the number of gates were not known until recently Kane and Williams [STOC 2016] showed that depth 2 linear threshold circuits with \(o(n^{3/2}/\log ^3 n)\) gates cannot compute an explicit function computable in linear time.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Suguru Tamaki

摘要

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 \textrm{poly}(\log n)}\right) ^a\right) }\) for some constant \(a>0\) . Our algorithm runs in time super-polynomially faster than \(2^n\) if \(m=O(n^2/\log ^b n)\) for some constant \(b>0\) . Previously, such algorithms were only known for bounded depth circuits with linear threshold gates and a slightly super-linear number of wires [Impagliazzo-Paturi-Schneider, FOCS 2013 and Chen-Santhanam-Srinivasan, CCC 2016]. We also show that depth 2 circuits with \(O(n^2/\log ^b n)\) symmetric and linear threshold gates in total cannot compute an explicit function computable by a deterministic \(2^{O(n)}\) -time Turing machine with an NP oracle. Previously, even slightly super-linear lower bounds on the number of gates were not known until recently Kane and Williams [STOC 2016] showed that depth 2 linear threshold circuits with \(o(n^{3/2}/\log ^3 n)\) gates cannot compute an explicit function computable in linear time.