On Norbert Blum’s claimed proof that P does not equal NP
lucatrevisan.wordpress.com
lucatrevisan.wordpress.com
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.
It's not purely intellectual pursuit. I am sure, eventually, there will be some applications of it.
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.
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)'
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’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 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.
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 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.
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 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".
Sounds like most academic paper reviews!
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 would invite you to read his earlier blog post on the same proof and then think about why he said what he did.
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.
>...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.
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.
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...
[1]: https://math.stackexchange.com/questions/2027182/how-do-we-p...
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...
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 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.
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.
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.
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.
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.
But that's not how mathematical proofs work.
But bottom line is that you're talking about something different.
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".
[1]: http://www.informit.com/articles/article.aspx?p=2213858
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.
Co-NP just seems so much harder than NP.
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.