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<k<1$ holds?


1 Answer 1


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

  • $\begingroup$ I guess we insert $OR$ layers (dummy) in between balanced $AND$ tree for $3$-CNF. $\endgroup$
    – User2021
    Apr 3, 2021 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.