Here is an interesting discussion about the relation to EXP and circuit complexity. https://mathoverflow.net/questions/58201/why-is-p-np-implies-exp-has-circuit

Here is an interesting discussion about the relation to EXP and circuit complexity. https://mathoverflow.net/questions/58201/why-is-p-np-implies-exp-has-circuit-of-2n-n-interesting-soft-philosoph https://mathoverflow.net/questions/58201/why-is-p-np-implies... A nice presentation by Wigderson may also help to see consequences of P=NP in a less rigorous phrasing ("'Creativity' can be efficiently automated [if P=NP]"). https://view.officeapps.live.com/op/view.aspx?src=https%3A%2F%2Fwww.math.ias.edu%2F~avi%2FTALKS%2FPvsNP.ppt&wdOrigin=BROWSELINK https://view.officeapps.live.com/op/view.aspx?src=https%3A%2... There is a more formal text as well: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06.pdf https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06.... Another class of results that I find interesting are inapproximability results. Namely, for certain NP hard problems, it is impossible to have a polynomial algorithm that computes the right value (for all instances) within a certain approximation factor unless P=NP. In https://dl.acm.org/doi/10.1145/1132516.1132612 https://dl.acm.org/doi/10.1145/1132516.1132612 Zuckerman shows that approximating MAX-CLIQUE is hopeless unless P=NP. This is of course just a mountain of evidence and not a proof. It does mean that there are potentially many ways in which one could prove P=NP without necessarily achieving anything practical. This is what I think Knuth means: you could have a non-constructive proof of P=NP or perhaps an algorithm with complexity n^10^10^10 that solves an NP-complete problem.