Mathematician Who Claimed 'P Is Not Equal To NP' Says His Proof Is Wrong (arxiv.org)

Earlier this month, Norbert Blum, a German mathematician, had published a research paper in which he implied that P is not equal to NP. The abstract of the post read: Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove exponential lower bounds for the monotone network complexity of the clique function and of Andreev's function. We show that these approximators can be used to prove the same lower bound for their non-monotone network complexity. This implies P not equal NP. Since the publication of that paper, several mathematicians have raised concerns with Blum's methodology, with some saying that there are flaws in it. Blum has now updated the research paper to add: The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time.

Comments

P = NP

[LordHighExecutioner]

Only if N = 1

That's what's good about critical thinkers

[MBGMorden]

It's refreshing to see people who will readily admit when they're wrong, since they're looking for the truth, not to prove a point.

That's always what I fall back two when people compare science to a religion: religion relies on faith - sticking to your beliefs no matter the evidence presented. Science will readily toss out everything they know and start over if something is proven to be wrong.

Re:That's what's good about critical thinkers

[31415926535897]

I was about to mod you up after reading your first sentence, but then the second came. Look, we all know of people who hop on the bandwagon of science and are as stubborn as anyone. There are also plenty of religious folk who use their brains (in the voice of Inigo Montoya, "You keep using that word faith. I do not think it means what you think it means").

Re:That's what's good about critical thinkers

[Captain Splendid]

Look, we all know of people who hop on the bandwagon of science and are as stubborn as anyone.

That's like judging the artistic merit of a band by focusing on their groupies. When the faithful criticize scientists, they're not using those arguments anyway.

There are also plenty of religious folk who use their brains

Unfortunately, they're in the minority and not anywhere near as loud-mouthed as their fundie brethren.

Re:That's what's good about critical thinkers

[Anonymous Coward]

Apples and oranges in a sense though.

Religion concern itself with "why".
Science concerns itself with "how".

Re:That's what's good about critical thinkers

[sacrilicious]

Sure, there are exceptions. But the GP's point is solid: the fundamental process in science is working from facts to supporting models, and the fundamental process in faith is working from models to supporting facts. They are indeed opposites, and various degrees of exceptions to them does not change their stated missions nor their overarching patterns of practice.

Re:That's what's good about critical thinkers

[Anonymous Coward]

If the "why" is irrelevant or meaningless, then a human being has as much value as a rock, and both will be nothing more than different Lego structures.

Re:That's what's good about critical thinkers

[Strider-]

That's always what I fall back two when people compare science to a religion: religion relies on faith - sticking to your beliefs no matter the evidence presented. Science will readily toss out everything they know and start over if something is proven to be wrong.

That's a pretty narrow definition of religion. For a significant, but less vocal part of religious folk, faith and science are more or less orthogonal. Scientific exploration and explanation doesn't eliminate faith, and religion doesn't deny science.

For me, the main intersection between Faith and Science is in the realm of ethics. It's not whether a certain piece of research is good or bad, but whether does it help to achieve what we're commanded to do... Help the poor, feed the hungry, be good stewards of creation.

Re:That's what's good about critical thinkers

[Anonymous Coward]

I was about to mod you up after reading your first sentence, but then the second came. Look, we all know of people who hop on the bandwagon of science and are as stubborn as anyone.
That's why MBGMorden used "science" and "religion" not "scientists", and "religious people". People can be stubborn and non-corrective, but science as a whole corrects itself. In the same vein, Religion (western at least) sticks to ideas like nothing else. How many hundreds of years did it take for the Catholic church to admit that maybe it shouldn't have punished Galileo?

Look no further than the books of each craft. Science books change all the time. Go find some Geology books from the 1940s, and you'll see crazy explanations we now know are wrong about what causes Earthquakes. Those ideas died out after Plate Tectonics took over in the 1950s or so.

By contrast, the Bible was canonized long, long ago and can't change. Religion changes very, very, very slowly. Much of the change is do to splinter groups forming and going off and doing their own thing. That's the perfect example of inflexibility. Splinter factions don't really happen much in science, and when they do, it's temporary until there's more data available, and consensus forms. Try that in religion!

Re:That's what's good about critical thinkers

[alvinrod]

Science is still practiced by people who can be pig-headed and stick to their guns long after it has become apparent there is no basis for them or will be reluctant to accept some new information that seems to turn the field on its head. It's something of human nature to cling to an initial belief despite good evidence to the contrary.

The important part is that mathematics and science give us the means to verify our beliefs (or at least in the case of science to test and reject other possible explanations) as the universe is under no obligation to conform to a mistaken belief. Religion has no such methods.

Re:That's what's good about critical thinkers

[drew_kime]

The fundamental process in science is working from facts to supporting models, and the fundamental process in faith is working from models to supporting facts.

That's the most concise description I've ever seen of that distinction. Stealing that. Thanks.

Re:That's what's good about critical thinkers

[dcollins]

Math is notably better on this score than the other sciences. I can think of other mathematicians who did a 180 and had to say "I was wrong", within a few days of a major publication, due to to critical objections. I can't think of any like that for natural sciences.

Re:That's what's good about critical thinkers

[gweihir]

Which makes religion subject to evolution (if the belief is stupid enough, its follower eventually die out) and science highly adaptive. Of course, you do only get concrete absolute truth in religion, (in Mathematics, you get absolute truth too, but it will be abstract and applicability to reality will never be absolute), and many people are looking for that, probably because they cannot deal with uncertainty. So the other thing about religion is that it uses its "truths" merely as mechanism to acquire and control its followers, truth is completely irrelevant (apart from the evolution angle).

Will be interesting to see whether Blum or somebody else can fix the proof. May take a while though.

Re:That's what's good about critical thinkers

[gweihir]

Not really. Religion is dumb. Literally. However there are quite a few people that use Science as a surrogate for religion and that corrupts science and makes it religion. For science you need an open mind. A main aim of religion is to close minds so that they do not go run off to the competition.

Re: That's what's good about critical thinkers

[Anonymous Coward]

Objectively, that is true. Human beings and rocks are basically the same thing, from a universal context.

To he human beings themselves, though, it's clearly not true.

But we, the ones having this conversation, are human beings. Thus, human beings matter a great deal more than rocks in the only context that matters, our own. That importance is not hinged on any sort of "why" we exist. In fact, any hypothetical "why" that involves god(s) actually would reduce our importance. See Christians whose whole world view is based on how awful and useless we are as creatures.

Re:That's what's good about critical thinkers

[grasshoppa]

It's refreshing to see people who will readily admit when they're wrong, since they're looking for the truth, not to prove a point.

That's always what I fall back two when people compare science to a religion: religion relies on faith - sticking to your beliefs no matter the evidence presented. Science will readily toss out everything they know and start over if something is proven to be wrong.

While accurate, the problem today is that many "scientists" aren't actually "scientists" in the sense that they can accept fault. They are, in essence, treating science like a religion, complete with the dogma.

To a certain extent this has always been a problem in science. Those "famous" scientific feuds are proof of that ( static universe vs big bag springs to mind ). However, lately this seems to have ramped up to insane levels. I attribute this to the internet, actually; instant communication enables idiots to feel like experts, amplifying the underlying problems to record levels.

And before anyone says it; yes, politics have always, unfortunately, meddled in science. Big tobacco and oil are prominent examples, but do any of us really trust "scientific" studies financed by the food industry?

So while your statement is factually true, people have muddied the water quite a bit ( as they always do ).

Re:That's what's good about critical thinkers

[Archangel Michael]

Not Inigo, so answering for myself (not him/her)

Science vs Religion is framed this (GP Post) way for ego. There is no scientific reason why the two should be compared on the same plane, since they deal with totally different realms.

Lets take a well known example. The Bible says that God Created the earth, and mankind. IT doesn't say when (except "the beginning" horrible translation btw). There are people that have extrapolated out lineages and calculated the "age of the earth" at 6000 years (give or take), but I want to remind you, that the Bible itself doesn't say it is 6000 years old anywhere.

Science on the other hand is pretty much convinced it is millions of years old. I can't say "proven" because that is not something that is provable, but from a statistical point of view, it is not likely that it is only 6000 years old. ;)

My faith (biblically based) doesn't require the earth to be only 6000 years old, or millions of years old. What it has done, is proven that science cannot account for the sins of man. The story of the man and woman in the garden is instructive, because with all the knowledge we've gained over the years (6000 or a Millennia ) has itself proven true, we are technologically better off, but morally bankrupt in the process. Instead of being able to pick up a rock and kill our brother, we now have arms that can kill millions without ever seeing the destruction we inflict.

Or, to put it a different way

Your scientists were so preoccupied with whether or not they could, they didn’t stop to think if they should

For every technological achievement we have that is used for good, it is matched equally with the ability to harm to a larger and larger number of people. This lesson is buried in the beginning pages of the the book so many people have opinions of, but have never actually read.

Please read this, not as a slam against science, but rather as a defense against strawman arguments used to discredit a book, that is philosophical/moral and not scientific. Most books of faith are the same, btw, they don't usually deal with Science, but rather the moral character of man. They aren't even in the same playing space. BTW, I have the same critique of my bible thumping comrades who mix religion with science too. ;)

Science without morals is how we get Josef Mengele. Morals without truth (science) is how we get to burning witches. There is a place, side by side, for Religion and Science to co-exist.

Re:That's what's good about critical thinkers

[Anonymous Coward]

Science without morals is how we get Josef Mengele. Morals without truth (science) is how we get to burning witches

You imply that the only source of morals is religion. I vehemently dispute that. We can develop a moral code based on humanist principles from scratch, without the need to resort to sky fairies.

Re:That's what's good about critical thinkers

[MBGMorden]

So if God created the universe (something had to)

No, something didn't have to. Even in our own universe random chance exists. In a universe that hosts random chance, it's not out of line to suppose that it could have been born out of such.

Besides, that line of thinking leads to an infinite loop anyways. If because the universe exists "something had to create" it, then whatever created it also exists and in turn also must have had creator. And that creator, ALSO needs a creator, and so forth and so forth. It just doesn't hold weight. Eventually there has to point where we get to a level where something just *IS* and has no creator. It's no less logical to assume that that is the universe than it is to assume it's God.

Re: That's what's good about critical thinkers

[naubol]

What world do you live on where any of this is true? Our information "super highway" is being used to tear the world apart. People are being indoctrinated not educated.

Citation please. It's being used for a lot of things and it's definitely disruptive. In the aggregate, over the long haul, is it a force for good or evil? Hard to say. It's also hard to point to the mess of interactions and blame destabilizing political events on it.

We can make some solid claims: science is making it cheaper to produce consumer goods, to produce life saving drugs, and to increase the carrying capacity of the planet. Poverty is decreasing globally and literacy is increasing globally and this is likely due to the aforementioned reasons.

Moreover, it does not seem to me that we can even make a claim that the world is being torn apart. Brexit is the most peaceful secession in history, it seems. For a long time, the great powers of the world have not been in active war with each other. ISIS gets much more ink than it deserves, its terrorism is a rounding error in deaths caused and it's almost certainly not a threat to the existence or prosperity of western civilization. Quality of life and political stability seem to be increasing in a general sense in the third world.

Where is your proof that things are being torn apart? Is it because your cousin voted for someone you dislike and has the gall to post irritating memes about it on Facebook?

Re: That's what's good about critical thinkers

[AmericaRunsOnDunkin]

Thus, human beings matter a great deal more than rocks in the only context that matters, our own.

Typical arrogant thinking from squishy water bags. You have neither the strength and constancy of granite, nor the adaptable and accommodating nature of limestone. Puny carbon sludge.

Rock Lives Matter!

Re:That's what's good about critical thinkers

[ChrisMaple]

Religious moral codes are completely arbitrary. They are based on the pronouncements of one person or a small group of people, but they have no causal relation to what actually promotes human lives. Most religious moralities conspicuously ignore the needs of human beings and proclaim that the purpose of man is to glorify God: if stupidity and hatred of mankind could be solidified into one sentence, that is it: "The purpose of man is to glorify God."

A proper morality starts by identifying the nature of human beings, and from that organizes a set of principles of behavior which will result in an objectively observable high quality of life for people. Science plays a role in helping to identify what humans are and what's good for them. Fictional creatures play no such role, and people who claim that fictional creatures play such a role often make life worse.

Attributing to lack of religion the mess that was 20th century Russia and China reveals a superficial and biased reading of history.

Re:That's what's good about critical thinkers

[Creedo]

BS. If what you said is true then China, the USSR, etc.. would not have happened or been put in check by the same moral code you claim can be adopted from nothing.

Non sequitur. Atheism != Humanism. And there is no reason to assume that atheistic, non-humanist regimes will develop humanistic moral codes.

Scientific facts: Not everyone is moral, not everyone has the same values, and not everyone has the desire or capacity to learn.

Not having the same values != not being moral. Again, the question of whether humanist morals can be derived from materialistic principles, true or false, has nothing to do with your statements.

Re:That's what's good about critical thinkers

[ag0ny]

Lets take a well known example. The Bible says that God Created the earth, and mankind.

And The Silmarillion clearly states in the Ainulindalë that Eru Ilúvatar created the Ainur, who in turn created Arda through their music.

You can't quote a book to justify your belief in an imaginary friend in the sky.

In one thing you're right: science and faith are in completely different realms. Science works with the real world and what can be demonstrated. Faith is just wishful thinking based on a delusion. It's perfectly fine to mock religion into oblivion until we finally get rid of this nonsense.

Re:That's what's good about critical thinkers

[evilbessie]

You know where the age comes from? Some monks added up the ages of people listed in the Torah and worked it out (they made some mistakes which is why Jesus is born in 4 or 6 BC. So yes the 6000 year old earth does indeed come from the bible itself.

Re:Who the fuck cares?

[Myrdos]

Once the debate is solved will anything change?

Only if the solution shows that P = NP.

Re:Who the fuck cares?

[geekmux]

Seriously. This debate always comes up. Does it have a practical purpose? Once the debate is solved will anything change?

Some analysis looks to open doors and our minds to new paths. Some looks to validate whether or not we should close doors and move on.

I am but a layman, but my understanding of P vs. NP targets the latter, not the former. Being efficient in our thinking always has value. Thinking you're traveling down a a dead end road vs. knowing you are, tends to steer efficiency.

Re:Who the fuck cares?

[Junta]

Maybe in a very academic sense, but practically speaking P != NP is overwhelmingly assumed to be the case, even if not proven. A valid proof of that being the case would be some buzz in the academics of math, but the rest of the world would shrug and move on.

Only for NP-complete problems.

[oldmacdonald]

Only for NP-complete problems.

not quite right

[oldmacdonald]

They haven't been proven to be NP-complete. There are certainly in NP.

I also have a proof his solution is incorrect

[dmatos]

Unfortunately, my proof cannot fit in the margins of this post.

Re:could there have been some editing on this titl

[Joce640k]

seriously, I expect better.

You must be new here.

Re:Who the fuck cares?

[gweihir]

And fail. High-exponent polynomials blow up similarly fast in practice, i.e. things become infeasible at very small sizes for worst-case scenarios. Incidentally, I know pretty much what I am talking about, including, for example, in crypto. The one-way function definition, for example, that stipulates P in one direction and NP for the reversal is simply broken and comes from theoreticians that have no insight into practice. It can be fixed (sort of), but you can do perfectly secure one-way functions using P only. Hence while you may have understood some of the math, you have failed to grasp what it means in reality.

Einstein / Hobbit / Spokane scablands

[epine]

Science is still practiced by people who can be pig-headed and stick to their guns long after it has become apparent ...

Einstein was criticized for sticking to his crackpot "general" theories in later life and not jumping onto the quantum bandwagon he himself had originally piloted out of the shuttle bay. But ask yourself this: did the world actually need Einstein working on quantum physics, or were all the other brilliant people involved more than sufficient?

If the stubborn Einstein had not persisted down his stubborn path, would we now be collectively guessing what might have been in the one and only Einstein had not nestled himself in the cockpit of the alien wormhole shuttle to unimagined physics?

Instead of yammering on about this old arrogance morality tale (oh, tiresome prose!) how about bringing some actual cost/benefit to the table?
____

You know, in that horrible movie, The Hobbit, I wasn't going to believe they couldn't open that stone door until there was 14 skeletons lying beneath it. If you're going to rattle the handle to the dragon's lair, the least you can do is stick to your guns (and your magic moon map).
_____

For anyone interested the sociology of science, or the immensity of planet earth itself, or just in it for some mind-blowing pictures, I can't recommend the following article strongly enough:

Formed by Megafloods, This Place Fooled Scientists for Decades — 9 March 2017

"Bretz was making arguments, and no one was going into the field to see anything," Baker said. "They were just countering his arguments with theory." And because scientists are first and foremost human beings, they're loathe to change their theories or their minds because of mere data.

Baker told me a story as we looked out at Palouse Falls, another dramatic cataract at the head of a massive canyon, with a stream running through it that seems comically out of scale, like a toddler wearing a grown man's boots. Sometime in the late 1950s or early '60s, a geologist named Aaron Waters brought one of Bretz's most vocal critics—James Gilluly, the one who'd called his ideas "preposterous" and "incompetent"—to the scablands for a first-hand look. As they took in the sight of the falls and the canyon, Gilluly was dumbfounded by their scale. "Gilluly was just quiet the whole time," Baker said, "and as they were leaving, he broke out into this immense laugh and said, 'How could anybody be so wrong?'" After resisting Bretz's theory for decades, simply seeing the landscape with his own eyes had changed his mind.

I often visited Drumheller and the surrounding badlands in my childhood. Amazing place. Never been to Spokane, but it's not that far away.
____

Grow up. Stubbornness is a virtue every damn time stubbornness works.

The exceptions are so rare, Herzog made a movie about it, with the entire cast in character the whole wretched time.

Aguirre, the Wrath of God

Kudos to him

[rraylion]

retracting his proof this quickly and acknowledging error takes fortitude and a type of perseverance not often seen.

Bravo in the attempt

Re:Who the fuck cares?

[swillden]

Maybe in a very academic sense, but practically speaking P != NP is overwhelmingly assumed to be the case, even if not proven. A valid proof of that being the case would be some buzz in the academics of math, but the rest of the world would shrug and move on.

A proof of P=NP, however, would be earthshaking well outside of academia. A constructive proof of P=NP, meaning a proof that contains a recipe for converting an NP problem into a P problem, could well be the single most important mathematical proof of all time, in terms of what it would enable people to do.

Actually, it's the very momentous impact of such a proof that makes everyone assume that P != NP. It's an intuition that the universe just isn't that nice, that there just have to be plenty of incredibly hard problems. Of course, there are problems that are harder than anything in NP, the NEXPTIME problems and, of course, the undecidable problems, so even if N = NP we'll still know we can't solve everything.