The most prominent computer scientist who believes it is Knuth. In the interview Twenty Questions for Donald Knuth, they explain that they believe P=NP but there is no constructive proof, only a doubly-negated classical proof that the assumption P≠NP leads to contradiction.
A poll from 2012 has more detailed information. In that poll, about 9% of respondents directly indicated some belief that P=NP.
I’m not sure where it first appeared, but in the folklore, the algorithms already exist. In particular, they mention Levin’s universal search algorithm, which enumerates all Turing machines and looks for the first one that solves the given problem. As I understand it, If P=NP then Levin’s algorithm is in P. Since I think that Knuth knows this too, I expect that he means that we won’t find the proof.
I think you misunderstood what I was asking. Baffling for me is that he is saying that there probably exists a proof-by-contradiction of NP problems can be solved in P, but he is skeptical about finding an actual algorithm that solves NP problems in P. i.e. saying that something exist in principle, but we will most likely not find it.
This problem is entering pop-science big time. I expect there to be a Holywood blockbuster about it soon (update: there is one already https://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film)
But is there someone that actually thinks that P=NP?
The most prominent computer scientist who believes it is Knuth. In the interview Twenty Questions for Donald Knuth, they explain that they believe P=NP but there is no constructive proof, only a doubly-negated classical proof that the assumption P≠NP leads to contradiction.
A poll from 2012 has more detailed information. In that poll, about 9% of respondents directly indicated some belief that P=NP.
I don’t understand what he means. If it is equal, then the algorithm should exist. But then why does he say that we will not find it?
I’m not sure where it first appeared, but in the folklore, the algorithms already exist. In particular, they mention Levin’s universal search algorithm, which enumerates all Turing machines and looks for the first one that solves the given problem. As I understand it, If P=NP then Levin’s algorithm is in P. Since I think that Knuth knows this too, I expect that he means that we won’t find the proof.
I think you misunderstood what I was asking. Baffling for me is that he is saying that there probably exists a proof-by-contradiction of NP problems can be solved in P, but he is skeptical about finding an actual algorithm that solves NP problems in P. i.e. saying that something exist in principle, but we will most likely not find it.
What a great series of questions and answers! Thanks for linking this.