## Thursday, September 28, 2023

### Half-Exponential No More

I've mentioned Kannan's proof that $$\Sigma_2^p$$ does not have $$n^2$$ size-circuits before. A similar proof shows that $$\Sigma_2^E = \mathrm{NTIME}^\mathrm{NP}(2^{O(n)})$$ does not have polynomial-size circuits in general. You can create a language in the third-level of the exponential-time hierarchy that has maximum circuit complexity. Now if SAT doesn't have poly-size circuits you are done. Otherwise the polynomial-time hierarchy collapses to $$\Sigma_2^p$$ which means the exponential-time hierarchy collapse to $$\Sigma_2^E$$.

Can you show $$\Sigma_2^E$$ has near exponential-size circuit complexity? The above proof doesn't quite work. The problem is that while a polynomial of a polynomial is polynomial, a subexponential function of a subexponential function could be superexponential. You can only make the proof work for circuit-size half-exponential, i.e., function $$f$$ such that $$f(f(n)) = 2^{o(n)}$$. I don't know of any natural half-exponential functions, but they are much larger than quasi-polynomial and much smaller than exponentials.

The best known smallest class with an exponential circuit lower bound is for $$\Delta_2^E=E^{\Sigma_2^P}$$ due to Miltersen, Vinodchandran and Watanabe from the last millennium.

Lijie Chen, Shuichi Hirahara and Hanlin Ren have a new paper showing that in fact $$\Sigma_2^E$$ does require exponential-size circuits. They have the same bound for smaller classes if you allow a bit of advice.

You've seen these authors names before in this blog. The future of computational complexity is in good hands.