UC San Diego

Proving circuit lower bounds is one of the most difficult tasks in computational complexity theory. The NP vs. P/poly problem asks whether there are small non-uniform circuits that can simulate circuit satisfiability. The answer is widely believed to be false, but so far progress has only been made in the case of restricted circuits. In the 1980s the progress stalled after it was shown that NP doesn’t have non-uniform AC0 circuits that have MOD-m gates for any prime m. After almost three decades, in the 2010s Williams made progress in the relaxed case of NEXP lower bounds. He first showed that non-trivial satisfiability algorithms for a circuit class entail NEXP lower bounds against that class. Then he designed a fast satisfiability algorithm for ACC circuits (AC0 circuits with MOD-m gates for any constant m) to show that NEXP doesn’t have non-uniform ACC circuits.

We make progress in bringing down the class NEXP, specifically by limiting non-determinism (in terms of the number of non-deterministic branches that accept). We show that slightly faster satisfiability algorithms entail lower bounds for UEXP and related classes. We believe this is progress towards making similar connections, and thus proving lower bounds, for EXP and lower complexity classes.

To investigate why progress again stalled around ACC lower bounds, and why TC0 (AC0 circuits with majority gates) lower bounds have not been established yet, Williams made rigorous connections between NEXP lower bounds and variations of Natural Proofs. Razborov and Rudich defined Natural Proofs to showcase the limitations of the current lower bound techniques. They showed that any technique that entails Natural Proofs, i.e. Proofs that are (i) constructive, (ii) useful, and (iii) large, fail to prove strong lower bounds. Williams showed that NEXP lower bounds, regardless of the technique, entail Proofs that satisfy the first two of the three conditions of Natural Proofs.

We make Williams connections more rigorous, and show that UEXP lower bounds entail Proofs, that in addition to the first two conditions of Natural Proofs, satisfy a third condition that is exactly the opposite of largeness condition. We call this condition, the uniqueness condition, and these Proofs, the Unique Proofs. These connections showcase that NEXP -> UEXP -> EXP is a viable path to approach EXP lower bounds.

We also discuss an alternate approach to improve NEXP lower bounds. We define a new form of non-determinism to capture the non-uniform circuits from the class (NP \cap coNP)/poly, and call it promise-Single-Valued non-determinism. We show that in the current NEXP lower bounds, we can allow the non-uniform circuits some limited non-determinism (in terms of the number of non-deterministic inputs) of the type promise-Single-Valued. We also discuss how small improvements in the amount of this special type of non-determinism, even in the restricted circuits much weaker than ACC, would imply very strong lower bounds such as NEXP not in P/poly.