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?


If such an algorithm were found, it would violate the exponential time hypothesis. See also, for example, Are there subexponential-time algorithms for NP-complete problems?.

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).

Beyond that, I don't think there would be any other obvious consequences. In particular, I don't know of any significant consequences if the ETH is violated (other than the obvious one, that the theorems of the form "if the ETH holds then..." become moot).

| cite | improve this answer | |
  • $\begingroup$ I think it is only the first part of your answer which is relevant. It also begs the question, what are the consequences of violating the ETH. $\endgroup$ – Lembik Jun 2 '14 at 6:52
  • 1
    $\begingroup$ @Lembik, why do you think the rest of my answer is not relevant? As far as begging the question, if the original user wanted to what the consequences of violating the ETH are, he/she should have asked that -- but as a bonus, I already answered that question in the last line of my answer (I already explained the consequences of violating the ETH). So I'm not sure where you're going with your comment. Would you like to elaborate? $\endgroup$ – D.W. Jun 2 '14 at 6:53
  • $\begingroup$ The second paragraph in your answer answers a different question. That's all he meant I think. In relation to the consequences of violating the ETH, it would be great if you could expand in your answer. I suppose the main consequences are just that you don't get the list of consequences given on the wiki page but maybe there is something more interesting. $\endgroup$ – user10101 Jun 2 '14 at 8:30
  • $\begingroup$ @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. $\endgroup$ – D.W. Jun 2 '14 at 18:22
  • $\begingroup$ 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. $\endgroup$ – user10101 Jun 2 '14 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.