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

[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

[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

[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: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?

[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.

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.