# NP-complete problems and sub-expenential sized circuits

If one were to show that an NP-complete problem had $2^{n^{O(1)/\log{\log{n}}}}$ circuit complexity, what would the consequences of this be?

And of course, if this were the best possible complexity for any algorithm for this problem, you would have shown that $P \ne NP$ (and in fact that $NP \ne P/\text{poly}$). When you wrote that the problem has such-and-such circuit complexity, I don't know whether you meant (a) there exists an algorithm with that complexity, or (b) the problem has that complexity (which means there exists an algorithm of that complexity, and there is no better algorithm); this paragraph only applies if you meant (b).
• @user10101, thanks for the comment. I don't know how of any other consequences (e.g., I don't know of anything more interesting), so I don't know how to elaborate any further. Maybe someone else will. As far as the second paragraph, the reason that is relevant is because the question asks us to suppose that the problem has complexity such-and-such. When we say that a problem has complexity $T(n)$, we mean (i) there exists an algorithm with complexity $T(n)$, and (2) there is no algorithm with smaller complexity. It is part (2) that makes my second paragraph relevant to this question. – D.W. Jun 2 '14 at 18:22
• Good point re: complexity $T(n)$. I meant an upper bound which I thought was implied by the $O(1)$ term but maybe that wasn't clear from how I said it. – user10101 Jun 2 '14 at 21:27