On Norbert Blum’s claimed proof that P does not equal NP(lucatrevisan.wordpress.com)
lucatrevisan.wordpress.com
On Norbert Blum’s claimed proof that P does not equal NP
https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal-np/
73 comments
It's not like nobody's ever tried this before. There's many experts that have probably committed years if not more to understanding this and would be in a very good position to evaluate this paper due to their depth of knowledge.
In about 3-4 years you'll come to realize it's about ego.
> Their love and devotion to purely intellectual pursuits should really be appreciated every once in awhile.
It's not purely intellectual pursuit. I am sure, eventually, there will be some applications of it.
It's not purely intellectual pursuit. I am sure, eventually, there will be some applications of it.
> It's not purely intellectual pursuit.
I feel like you don't really understand theoretical mathematicians. Application is a side effect of the highest maths, not a goal of its practitioners.
I feel like you don't really understand theoretical mathematicians. Application is a side effect of the highest maths, not a goal of its practitioners.
Some interesting ongoing discussion (last post an hour ago):
https://cstheory.stackexchange.com/questions/38803/where-is-...
In particular someone claimed to have found a flaw (which I can not comment on, not a complexity theory person):
'Tardos' function is a monotone function which is 1 on k-cliques and 0 on complete (k-1)-partite graphs. As far as I can tell, Berg and Ulfberg use ONLY these properties in their CNF-DNF approximation proof for CLIQUE, which hence prove that Tardos' function has exponential monotone complexity. Blum's Theorem 6 says that monotone complexity lower bounds by CNF-DNF approximation for monotone functions, give the same NON-monotone lower bound. Hence, Tardos' function have exponential complexity according to Theorem 6 (which is false)'
https://cstheory.stackexchange.com/questions/38803/where-is-...
In particular someone claimed to have found a flaw (which I can not comment on, not a complexity theory person):
'Tardos' function is a monotone function which is 1 on k-cliques and 0 on complete (k-1)-partite graphs. As far as I can tell, Berg and Ulfberg use ONLY these properties in their CNF-DNF approximation proof for CLIQUE, which hence prove that Tardos' function has exponential monotone complexity. Blum's Theorem 6 says that monotone complexity lower bounds by CNF-DNF approximation for monotone functions, give the same NON-monotone lower bound. Hence, Tardos' function have exponential complexity according to Theorem 6 (which is false)'
As far, as I understand Blum's paper, he doesn't talk about general non-monotone networks, but rather about "standard networks", where all 'not' gates are moved to the front: "The resulting network is a so-called standard network where only input variables are negated."
Could it be, that Tardos' function has exponential monotone network complexity, exponential standard network complexity (with inverters allowed at front), but polygonal complexity in general networks (with not gates/inverters also allowed in the middle)?
Could it be, that Tardos' function has exponential monotone network complexity, exponential standard network complexity (with inverters allowed at front), but polygonal complexity in general networks (with not gates/inverters also allowed in the middle)?
I'm 90% sure the first paper proving P!=NP will either use a Kolmogorov complexity argument, or an exact enumeration involving a semigroup problem that is exponential.
Any clarification on how you expect such arguments to be used? Otherwise your claims are completely out of left field, because most approaches are not anything along those lines.
Kolmogorov had an outline of an attempt using Kolmogorov Complexity to settle P vs NP. I do not unfortunately recall the crux of the argument. This was formulated in the 1970s, and has not been followed up as far as I know. On the other hand, given Baker-Gill-Solovay and the Natural Proof barriers, no proof settling the question is expected to be easy.
Scott Aaronson is confident that it will be refuted by the end of the week:
> I’d again bet $200,000 that the paper won’t stand [...] and if the thing hasn’t been refuted by the end of the week, you can come back and tell me I was a closed-minded fool.
http://www.scottaaronson.com/blog/?p=3389
On the other hand, his original post contained an short explanation (one or two sentences) what he believed to be a flaw in the paper, which he has removed since then.
> I’d again bet $200,000 that the paper won’t stand [...] and if the thing hasn’t been refuted by the end of the week, you can come back and tell me I was a closed-minded fool.
http://www.scottaaronson.com/blog/?p=3389
On the other hand, his original post contained an short explanation (one or two sentences) what he believed to be a flaw in the paper, which he has removed since then.
FWIW,
I think Aaronson's dismissive attitude is unbecoming and disrespectful amongst colleagues.
'Unrelated Update: To everyone who keeps asking me about the “new” P≠NP proof: I’d again bet $200,000 that the paper won’t stand, except that the last time I tried that, it didn’t achieve its purpose, which was to get people to stop asking me about it. So: please stop asking, and if the thing hasn’t been refuted by the end of the week, you can come back and tell me I was a closed-minded fool.'
Quick-copy pasting a Facebook comment as reason not to want to deal with it, betting a large sum of money almost tauntingly is not good scholarship.
A serious researcher made a serious effort to solve a problem. Say you have not verified it and don't want to comment.
It almost seems like he does not want P/NP to be proven because he has made a reputation by becoming an authority on dismissing attempts.
I think Aaronson's dismissive attitude is unbecoming and disrespectful amongst colleagues.
'Unrelated Update: To everyone who keeps asking me about the “new” P≠NP proof: I’d again bet $200,000 that the paper won’t stand, except that the last time I tried that, it didn’t achieve its purpose, which was to get people to stop asking me about it. So: please stop asking, and if the thing hasn’t been refuted by the end of the week, you can come back and tell me I was a closed-minded fool.'
Quick-copy pasting a Facebook comment as reason not to want to deal with it, betting a large sum of money almost tauntingly is not good scholarship.
A serious researcher made a serious effort to solve a problem. Say you have not verified it and don't want to comment.
It almost seems like he does not want P/NP to be proven because he has made a reputation by becoming an authority on dismissing attempts.
No, it's because one could spend a hundred lifetimes showing incorrect P vs NP proofs. Either he is right, or if the author is convinced of the disrespect they can $200,000.
Most people who publish proofs don't seem to make any attempt to get their work reviewed before putting it out onto the open internet. That's of course their choice, but then you have to expect people to tell you where you have wrong, bluntly. It's a huge waste of everyone's time who then reads the proof.
Most people who publish proofs don't seem to make any attempt to get their work reviewed before putting it out onto the open internet. That's of course their choice, but then you have to expect people to tell you where you have wrong, bluntly. It's a huge waste of everyone's time who then reads the proof.
I don't think his dismissiveness is aimed at his colleagues, but rather to the commenters on his blog. Aaronson's public persona has resulted in him getting mobbed by requests-for-comment from the general public every time there's some news about theoretical CS (or D-Wave), which I'm sure is what happened here. I imagine it gets tiring after a while, like actors constantly being asked to repeat some catchphrase.
I think he could respond to it better (once you're a public-enough figure online, a good skill to learn is knowing when to step away from the keyboard instead of saying something grumpy you'll probably later regret), but I see where he's coming from.
I think he could respond to it better (once you're a public-enough figure online, a good skill to learn is knowing when to step away from the keyboard instead of saying something grumpy you'll probably later regret), but I see where he's coming from.
As a researcher, I think he is dismissive of Blum's work.
Let's take a moment to change perspective:
Imagine you worked for years on something and finally uploaded it on ArXiv, waiting for the community to weigh in. The following characters appear:
1. Someone known in the field does not bother reading it but says you are probably wrong, bets money on you being wrong and says he does not want to be bothered with it. How would you feel?
2. Someone else known in the community starts collating information/comments to help verify the proof or find instructive mistakes.
3. Another mathematician also believes Blum is wrong just because it is statistically likely, and does not want to spend time on something that will most likely lead nowhere. She keeps this opinion to herself and simply does not engage with the material. If approached, she declines to comment because she says he did not have time to check the proof.
Aaronson went for option 1 and in my highly personal opinion, it's the worst of the ones listed. It's standing at the sidelines being snarky. Just because he may as well be right does not make this behaviour any better.
It is the equivalent of laughing in an undergrad lecture when someone asks a naive question.
Let's take a moment to change perspective:
Imagine you worked for years on something and finally uploaded it on ArXiv, waiting for the community to weigh in. The following characters appear:
1. Someone known in the field does not bother reading it but says you are probably wrong, bets money on you being wrong and says he does not want to be bothered with it. How would you feel?
2. Someone else known in the community starts collating information/comments to help verify the proof or find instructive mistakes.
3. Another mathematician also believes Blum is wrong just because it is statistically likely, and does not want to spend time on something that will most likely lead nowhere. She keeps this opinion to herself and simply does not engage with the material. If approached, she declines to comment because she says he did not have time to check the proof.
Aaronson went for option 1 and in my highly personal opinion, it's the worst of the ones listed. It's standing at the sidelines being snarky. Just because he may as well be right does not make this behaviour any better.
It is the equivalent of laughing in an undergrad lecture when someone asks a naive question.
I think we're talking past each other and don't actually disagree. To clarify my last post: I don't approve of what Aaronson did. I think it was a dumb thing to say and (assuming my hypothesis is correct that he did it out of frustration at constantly being pestered to comment on CS news) he instead should've cooled off and, as you say, taken option 3. I think he was aiming his statements at his fans, not academia, and in his frustration forgot that there's no such thing anymore as a message only directed at one group.
I just want the problem with his behavior to be accurately diagnosed, because I think (again, I could be wrong) the solution is "better manage your temper with your non-academia fans" and not "rethink your relationship with other academics".
I just want the problem with his behavior to be accurately diagnosed, because I think (again, I could be wrong) the solution is "better manage your temper with your non-academia fans" and not "rethink your relationship with other academics".
Thank you for clarifying this
> Someone known in the field does not bother reading it but says you are probably wrong
Sounds like most academic paper reviews!
Sounds like most academic paper reviews!
But he didn't just come out and say it; he was responding to numerous people who were asking him about it.
Aaronson would far rather take option 3. The only reason he doesn't is that his fans won't let him.
He could take option 3 regardless of what his fans "won't let him" do.
I think he could respond to it better (once you're a public-enough figure online, a good skill to learn is knowing when to step away from the keyboard instead of saying something grumpy you'll probably later regret), but I see where he's coming from.
I have no personal familiarity with this specific instance, but your assessment is likely correct. "Putting out the fire with gasoline" is pretty common on the internet. I have seen celebrities on Twitter reply to something they did not like, only to be surprised and grumpy that their attempts to shut it down backfired and just resulted in more of the thing they did not want, plus additional collateral damage of various sorts.
I have no personal familiarity with this specific instance, but your assessment is likely correct. "Putting out the fire with gasoline" is pretty common on the internet. I have seen celebrities on Twitter reply to something they did not like, only to be surprised and grumpy that their attempts to shut it down backfired and just resulted in more of the thing they did not want, plus additional collateral damage of various sorts.
Did you click through to the post? 'weinzeirl's use of ellipsis makes the statement seem harsher than it actually was. Here's what you missed:
>...except that the last time I tried that, it didn’t achieve its purpose, which was to get people to stop asking me about it. So: please stop asking... [emphasis mine]
If Aaronson had directed his comments at the actual researcher or at anyone affiliated with them, I'd agree with you, but it's clear that he's directing them at generally unsophisticated social media users who are too email-happy.
>...except that the last time I tried that, it didn’t achieve its purpose, which was to get people to stop asking me about it. So: please stop asking... [emphasis mine]
If Aaronson had directed his comments at the actual researcher or at anyone affiliated with them, I'd agree with you, but it's clear that he's directing them at generally unsophisticated social media users who are too email-happy.
> I think Aaronson's dismissive attitude is unbecoming and disrespectful amongst colleagues.
I would invite you to read his earlier blog post on the same proof and then think about why he said what he did.
http://www.scottaaronson.com/blog/?p=456
I would invite you to read his earlier blog post on the same proof and then think about why he said what he did.
http://www.scottaaronson.com/blog/?p=456
Note - that post is from 2010, and was in fact about a different proof with a different author (Deolalikar). I don't disagree with you, btw.
Amongst colleagues, it certainly is. We should treat all genuine attempts to research and present any idea with equal respect, and not be irrationally attached, or hopeful, or dismissive towards anything.
However, among mainstream media and the public, considering the previous false claims to a proof, and given the extreme attention surrounding the question being studied, Scott's response demonstrates what a healthy level of skepticism looks like.
However, among mainstream media and the public, considering the previous false claims to a proof, and given the extreme attention surrounding the question being studied, Scott's response demonstrates what a healthy level of skepticism looks like.
[deleted]
> I think Aaronson's dismissive attitude is unbecoming and disrespectful amongst colleagues.
That is exactly how science works. You have to prove something before it's made a fact. Science operates completely on the notion that incorrect statements should be gotten rid of.
That is exactly how science works. You have to prove something before it's made a fact. Science operates completely on the notion that incorrect statements should be gotten rid of.
And the problem here is that a lot of people want to quickly equate, "someone published what they claim is a proof" with "someone proved it". Just like pop-sci media likes to equate, "someone observed a correlation between X and Y that is surprising and contradicts with previous results" with "scientists prove X causes Y".
[deleted]
[deleted]
Relevant XKCD:
https://xkcd.com/955/
https://xkcd.com/955/
Knuth on why he believes P = NP and what it means [see question 17]:
http://www.informit.com/articles/article.aspx?p=2213858
http://www.informit.com/articles/article.aspx?p=2213858
I read these things and I wish I could understand it with a cursory knowledge of mathematical theory, but alas, I'm left longing for understanding, because it seems like a really interesting debate.
I've been convinced P!=NP ever since I started studying semigroup lower bounds. Even black box group membership is exponential in the largest prime less than or equal to N. https://oeis.org/A186202
P!=NP seems to be the general sentiment, though we're still waiting on the proof :)
I share the same sentiment, but I think it could be that P!=NP is an unprovable statement. Could be that there's something fundamental about the nature of computing which makes it impossible to prove or disprove it.
I used to think this, too, but Aaronson changed my mind with the observation in [0] that, if P != NP is independent, then it would necessarily imply a lot of what we would demand from a constructive P = NP proof. In particular, we could get some pretty hilarious improvements on those exponents in NP-complete algorithms, to the point where they become tractable for day-to-day computing.
There is a sense in which any complexity class which is self-low is "physical", or analogous to machines which we might build by hand with modular designs. A self-low class doesn't gain any additional power when relativized with itself as an oracle, and this directly corresponds to building a physical machine out of smaller machine modules.
We know that P is self-low. It seems that the universe insists that either we are able to build machines which tractably solve NP-complete problems, or not, but there is no in-between position.
[0] http://www.scottaaronson.com/papers/pnp.pdf p28
There is a sense in which any complexity class which is self-low is "physical", or analogous to machines which we might build by hand with modular designs. A self-low class doesn't gain any additional power when relativized with itself as an oracle, and this directly corresponds to building a physical machine out of smaller machine modules.
We know that P is self-low. It seems that the universe insists that either we are able to build machines which tractably solve NP-complete problems, or not, but there is no in-between position.
[0] http://www.scottaaronson.com/papers/pnp.pdf p28
Something is only unprovable wrt an axiom set.
You can add new axioms to an existing axiom set that can be semi-decidably proved inconsistent given the rest of the axiom set.
https://en.wikipedia.org/wiki/Large_cardinal https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
For a theory of how to choose an axiom set probabilistically, see: https://intelligence.org/2016/09/12/new-paper-logical-induct...
You can add new axioms to an existing axiom set that can be semi-decidably proved inconsistent given the rest of the axiom set.
https://en.wikipedia.org/wiki/Large_cardinal https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
For a theory of how to choose an axiom set probabilistically, see: https://intelligence.org/2016/09/12/new-paper-logical-induct...
You can't just add arbitrary axioms. It's entirely possible to have a statement that's unprovable with any axioms mathematicians would consider reasonable.
An axiom can be wrong wrt the standard model for some first-order theory:
http://lesswrong.com/lw/g0i/standard_and_nonstandard_numbers...
But, demonstrating an axiom is inconsistent with the standard model of peano arithmetic or ZFC is in the general case uncomputable.
For example, an axiom that claims some program halts when it does not actually halt cannot in general be proved to be inconsistent wrt the standard model, because otherwise one could decide the halting problem.
But, demonstrating an axiom is inconsistent with the standard model of peano arithmetic or ZFC is in the general case uncomputable.
For example, an axiom that claims some program halts when it does not actually halt cannot in general be proved to be inconsistent wrt the standard model, because otherwise one could decide the halting problem.
There are many, many things that are most likely provable that have not been proven yet. Fermat's Last Theorem went 358 years before it was finally proven. Theoretical computer science is a very young field by comparison.
Years is a bad measure to use. The number of mathematicians has grown exponentially over the last 400 years. Both because of population growth and the Flynn effect, and because our society is a lot richer and we spend more on mathematical research.
On the other hand, can nine women have a baby in a month?
I don't think it's impossible to prove, I think we just aren't yet good at proving it.
One reason I believe P!=NP is I can imagine what a proof of P=NP would look like -- just write a C program that solves SAT or Sudoku or something, in polynomial time, and prove it's correctness and execution time. There are tens of thousands of papers which do that, for various problems.
I can't really imagine what a proof of P!=NP would look like, proving something doesn't exist is extremely hard, particularly because for any particular instance of an NP problem, there is a problem which solves it "by luck".
One reason I believe P!=NP is I can imagine what a proof of P=NP would look like -- just write a C program that solves SAT or Sudoku or something, in polynomial time, and prove it's correctness and execution time. There are tens of thousands of papers which do that, for various problems.
I can't really imagine what a proof of P!=NP would look like, proving something doesn't exist is extremely hard, particularly because for any particular instance of an NP problem, there is a problem which solves it "by luck".
Even if it'll be a constructive proof, it doesn't mean you could actually write the C program. It'll be like, here are the steps to construct an algorithm for this NP complete problem and then the number of steps itself is bound by n^(absurdly large number) and then prove the complexity is bound by n^(another absurdly large number). It will have zero practical consequences.
Maybe that could be a thing to prove.
Is it possible to prove that something is not provable?
Is it possible to prove that something is not provable?
> Is it possible to prove that something is not provable?
It's possible to prove that something is not provable within some axiom set. See: https://en.wikipedia.org/wiki/List_of_statements_independent...
It's possible to prove that something is not provable within some axiom set. See: https://en.wikipedia.org/wiki/List_of_statements_independent...
In general yes. [1] I don't know about PvNP
[1]: https://math.stackexchange.com/questions/2027182/how-do-we-p...
[1]: https://math.stackexchange.com/questions/2027182/how-do-we-p...
Yep. That's what Gödel did.
What if it is not computable?
I don't see how it could be unprovable.
As far as I know the only way a theorem can be unprovable is if it makes statements involving infinity.
You can reduce P vs NP to a question involving only finite sets by choosing some finite n, which can be arbitrarily large. It should be large enough so that the asymptotic behavior of any algorithm would dominate at n.
Instead of asking about the scaling behavior of an algorithm as n approaches infinity you now ask about its scaling up to the finite value n.
This is now a question about a finite set which has a definite answer which could, in principle, be determined by enumerating all possible algorithms (represented, for example, by boolean circuits with some large size bound) for a particular NP complete problem for problem sizes up to n. Of course this would probably take many times the lifetime of the universe to actually do, but it could be done in principle. So the question of how the minimum circuit size which solves an NP complete problem scales with n has a definite answer.
As far as I know the only way a theorem can be unprovable is if it makes statements involving infinity.
You can reduce P vs NP to a question involving only finite sets by choosing some finite n, which can be arbitrarily large. It should be large enough so that the asymptotic behavior of any algorithm would dominate at n.
Instead of asking about the scaling behavior of an algorithm as n approaches infinity you now ask about its scaling up to the finite value n.
This is now a question about a finite set which has a definite answer which could, in principle, be determined by enumerating all possible algorithms (represented, for example, by boolean circuits with some large size bound) for a particular NP complete problem for problem sizes up to n. Of course this would probably take many times the lifetime of the universe to actually do, but it could be done in principle. So the question of how the minimum circuit size which solves an NP complete problem scales with n has a definite answer.
> I don't see how it could be unprovable.
It's quite plausible that it's unprovable, although you would have to be specific about the axiom system you're using.
> As far as I know the only way a theorem can be unprovable is if it makes statements involving infinity.
It does.
> You can reduce P vs NP to a question involving only finite sets by choosing some finite n, which can be arbitrarily large. It should be large enough so that the asymptotic behavior of any algorithm would dominate at n.
No, you can't. You don't know how large that n has to be, so you have to prove it for arbitrarily large n, and that's the "infinity" that you're dismissing.
> Instead of asking about the scaling behavior of an algorithm as n approaches infinity you now ask about its scaling up to the finite value n.
So you've changed the question to one that can be proven. The original question might still be unprovable.
So I don't see how your comment really makes any sense at all. Perhaps you could be a little more precise.
It's quite plausible that it's unprovable, although you would have to be specific about the axiom system you're using.
> As far as I know the only way a theorem can be unprovable is if it makes statements involving infinity.
It does.
> You can reduce P vs NP to a question involving only finite sets by choosing some finite n, which can be arbitrarily large. It should be large enough so that the asymptotic behavior of any algorithm would dominate at n.
No, you can't. You don't know how large that n has to be, so you have to prove it for arbitrarily large n, and that's the "infinity" that you're dismissing.
> Instead of asking about the scaling behavior of an algorithm as n approaches infinity you now ask about its scaling up to the finite value n.
So you've changed the question to one that can be proven. The original question might still be unprovable.
So I don't see how your comment really makes any sense at all. Perhaps you could be a little more precise.
Say you let n be a number equal to all of the memory bits that currently exist on Earth then showed that the size of the smallest boolean circuit solving 3SAT for variable counts near n scaled as 2^n.
That would essentially be enough to convince me that P != NP.
It would be true for all practical purposes. In fact I would find the above information more interesting than the actual asymptotic behavior as n -> infinity.
That would essentially be enough to convince me that P != NP.
It would be true for all practical purposes. In fact I would find the above information more interesting than the actual asymptotic behavior as n -> infinity.
> It would be true for all practical purposes.
But that's not how mathematical proofs work.
But that's not how mathematical proofs work.
You're talking about something completely different. If you don't care about asymptotic behavior that's one thing, but you do need to recognise that you're talking about something different, and unless you are really clear and really precise you won't be able to communicate effectively with other people, even if what you say is relevant and important.
But bottom line is that you're talking about something different.
But bottom line is that you're talking about something different.
>enumerating all possible algorithms [...] for problem sizes up to n.
Please keep in mind that this includes an algorithm that has precomputed all possible solutions and retrieves their value from a list.
In fact I find it hard to say for certain that you can't for instance assume the existence of an algorithm that calculates the answers to some NP problem in constant time, but which takes an amount of time that can't be proven to be smaller than any other number. This would lead to a situation where P != NP may not be provable.
Please keep in mind that this includes an algorithm that has precomputed all possible solutions and retrieves their value from a list.
In fact I find it hard to say for certain that you can't for instance assume the existence of an algorithm that calculates the answers to some NP problem in constant time, but which takes an amount of time that can't be proven to be smaller than any other number. This would lead to a situation where P != NP may not be provable.
I think it's interesting that Knuth came to believe that P=NP. See question 17 and its response in this interview with him [1].
[1]: http://www.informit.com/articles/article.aspx?p=2213858
[1]: http://www.informit.com/articles/article.aspx?p=2213858
Yeah, proving it is not going to be much of a game changer. Most everyone already assumes it's true.
But if someone were to prove the opposite, the entire technology world would shift dramatically, so it will certainly help to have a proof for this.
But if someone were to prove the opposite, the entire technology world would shift dramatically, so it will certainly help to have a proof for this.
That is assuming the constant end up being in the realm of reasonable. `O(2^N)` and `O(N^1000)` are no different for any useful values of `N`.
Wouldn't someone proving it true be a game changer in that it would preclude the ability of anyone to prove the opposite?
I could be convinced that P=NP, but that would also mean that Co-NP=P and I just couldn't wrap my mind around that one.
Co-NP just seems so much harder than NP.
Co-NP just seems so much harder than NP.
I believe it's opposite i.e. if P=Co-NP, then P=NP.
This is all contained in the collapse of the hierarchy, no matter which way you look at it. It will all be the same.
So, P=NP implies P=Co-NP?
Yes. Since we already know that P=Co-P, if P were to be shown equal to NP then P=NP=Co-NP=Co-P.
All these classes would turn out to be the same since P is closed under complement. Then NP would be as well and everything is equal.
That's why this result sometimes is called the collapse if the complexity hierarchy.
All these classes would turn out to be the same since P is closed under complement. Then NP would be as well and everything is equal.
That's why this result sometimes is called the collapse if the complexity hierarchy.
Because P=Co-P, that's the same thing.
[deleted]
I have been convinced that P==NP since my first exposure to the topic in university. There are NP complete problems where I can really not imagine how they could be solved quickly, but vertex three coloring just looks so doable to me by some informal intuitive arguments. In another life I would devote my life to fleshing out the argument and proving P==NP. Or at least learn where my intuitive argument fails.
By definition, each NP-complete problem is provably as hard as another though. Graph coloring can be reduced in polynomial time to every NP-C problem. It doesn't really make sense to me that one problem can just "look so doable" when they're really just the same problems.
They are of course all reducible to each other but that doesn't necessarily mean that they are all equally hard to attack. That's very common in mathematics where reformulating the problem can make the relevant bits and pieces more obvious while the original formulations obfuscated them. In the same way some NP-complete problems look harder to me because they seem to require global information while vertex three coloring looks to me like it should be solvable with quite localized information. Another good analogy is probably the way switching between position and momentum eigenstates in quantum physics makes different problems easier to express and handle.
[deleted]
I am amazed by the speed with which mathematicians are able to quickly congregate and debate such things like this. It makes me excited to enter a graduate program knowing that people take academia so seriously. Their love and devotion to purely intellectual pursuits should really be appreciated every once in awhile.