Superlinear Wire Lower Bounds Toward P Versus NP

The satisfying inputs of a Boolean circuit with \(s\) inputs and wires in all can be counted in time \(2O(s/√log s)\) when every gate is either an arbitrary function of at most \(s4/5\) inputs or a threshold, exact, modular or symmetric gate of any fan-in with weights of at most \(s2/3\) bits. Consequently a language in \(ENP\) needs more than \(cN√log N\) wires in circuits on \(N\) inputs built from such gates, with arbitrary gates of at most \(N3/4\) inputs and weights of at most \(N1/2\) bits. The \(P\) versus \(NP\) problem remains open; we survey where these bounds stand within it.