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.
nice
ReplyDeleteSo E requires Exp size circuits implies P=BPP right? How far away are we?
ReplyDeleteThat's right but still pretty far. We don't know how to get over the relativization barrier.
DeleteAn added question.. you said only third level had exp circuits proof and this gave only half exp circuits for second level. Now since we have exp size circuits proof for second level, do we have half exp circuits size proof for first level which is Exp? So may be we are half way to P=BPP ;) ??
ReplyDeleteSince BPP has poly-size circuits, a half exp lower bound for EXP would imply BPP strictly in EXP. But for all we know, EXP, NEXP and even EXP^NP are in BPP and thus all have polynomial-size circuits. See Heller.
Delete