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

Circuits with fan-out 1 are called formulas.

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 $$kge1$$ 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 $$logloglog 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.