# Relevance of depth for $NP$-completeness of fan-in $2$ and fan-out $1$ modest depth circuits?

Let $$\mathcal C$$ be a circuit of $$m=f(n)$$ input wires

1. where every input is taken in the set $$\{x_1,x_1',\dots,x_n,x_n'\}$$ where $$x_n\in\{0,1\}$$ and $$x_n+x_n'=1$$ holds (not all $$x_i,x_i'$$ necessarily needs to be utilized if $$f(n)=o(n)$$)

2. where every layer of the circuit is all $$AND$$ or all $$OR$$ gates having fan-in $$2$$ and fan-out $$1$$, and the AND and OR layers alternate

3. depth of the circuit is $$\leq\log^kn$$ at a $$k\geq0$$

(essentially an $$NC^k$$ circuit having gates of fan-out $$1$$).

The question is whether $$\exists x_1,\dots,x_n\in\{0,1\}:\mathcal C(x_1,\dots,x_n)=1$$.

Usual $$NP$$-completeness is for $$CIRCUITSAT$$ where depth can be $$poly(n)$$ without restricting to fan-out $$2$$ and fan-in $$1$$. If depth is $$k=O(\log n)$$ do we still get $$NP$$-completeness if gates are fan-in $$2$$ and fan-out $$1$$ and number of input wires $$poly(n)$$?

Is it $$NP$$-complete at all fixed $$k\geq1$$ if $$f(n)=poly(n)$$?

If $$k=0$$ the problem is in $$P$$ because the number of input wires is $$O(1)$$.

Is there a complexity class for the problem if $$0 holds?

Polynomial-size fan-in 2 formulas of arbitrary depth can be rebalanced to depth $$O(\log n)$$ by Spira’s lemma, hence they compute exactly nonuniform $$\mathrm{NC}^1$$. (The restriction that layers alternate between AND and OR is immaterial, as one can always insert dummy nodes to make it true, while at most doubling the depth.) Thus, your model with $$k\ge1$$ collapses to $$k=1$$.
Satisfiability is NP-complete already for 3-CNF. These can be written as depth $$O(\log n)$$ fan-in 2 formulas by arranging the outer conjunction as a balanced binary tree. (Again, one might insert dummy OR gates to make the connectives alternate if desired.)
For $$k<1$$, the formula only depends on $$2^{(\log n)^k}$$ variables, and therefore its satisfiability is computable in time $$2^{O(2^{(\log n)^k})}$$. Thus, it cannot be NP-complete unless ETH fails. There is no special complexity class for it, it is just NP scaled down to inputs of size $$2^{(\log n)^k}$$.
Better, satisfiability of circuits of depth $$(\log n)^k$$ for $$k<1$$ is not NP-complete unless P = NP: if it is NP-complete, then there exists a poly-time reduction $$f$$ of CIRCUIT-SAT to itself that maps a circuit of size $$n$$ to a circuit of size $$2^{O((\log n)^k)}$$. Using $$\log\log\log n/\log(k^{-1})$$ iterations of $$f$$ (which are computable in polynomial time), we reduce CIRCUIT-SAT to satisfiability of a constant-size circuit, which is trivial to decide.
• I guess we insert $OR$ layers (dummy) in between balanced $AND$ tree for $3$-CNF. Apr 3 at 8:07