15 ms·

> To be honest, I doubt that people who can actually make any progress in these areas would fail to know already what you are saying. I hope you are correct :-

> To be honest, I doubt that people who can actually make any progress in these areas would fail to know already what you are saying. I hope you are correct :-) > There are many results that show very weird consequences for having P=NP. So either the nature of computing is utterly bizarre or in fact there are many common problems which are simply impossible to solve exactly in a reasonable amount of time. Wow, that's very interesting! Can you recall an example or two of such consequences? I would be really interested in reading about that. Edit: Donald Knuth seems to believe that P=NP and also says there would be no major implications if we found such a proof... > You can of course try to find good heuristics that cover some common cases or even approximations of NP hard problems in some cases. There are literally thousands of researchers doing that every day. Completely agreed! Perhaps you are right and my worries are unfounded.

dellamonica 4y ago
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.

dellamonica 4y ago

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.