For one moment I read it as the Claymation institute.
Yes, I am sad.
Computer science boffin Norbert Blum has acknowledged that his P≠NP proof is incorrect, as a number of experts anticipated. In a post published Wednesday to the arXiv.org page where his paper used to be, Blum, a computer science professor at the University of Bonn, said: "The proof is wrong. I shall elaborate precisely what …
Not this time, though.
My thinking is that it's unlikely to be true, and if it's true I'll be so amazed and happy that I don't mind losing the money.
But I like the Bayesian look at this. The prior is really quite informative in his algorithm ;)
Thing is it seems that attempts to prove and disprove the conjecture have failed.
So the fails are not biasing the result, Bayesian style, toward a particular direction.
Although strictly speaking even failures are fine, if they teach you something more about the solution space, IE where a solution (if it exists at all) must be found.
"Could it be that P≠NP is unprovable."
That would be possible. From a practical point of view, the consequences would be not so different from a proof that P≠NP. It would still mean that you cannot have an actual polynomial-time algorithm to solve, say, the traveling salesman problem (because any such algorithm would immediately be a proof that P=NP).
However, it would mean that *assuming* that such an algorithm exists (even though you don't know it) cannot lead you to a logical contradiction.
"and if so, could someone prove this to be the case?"
I take this as a question if proving this would be possible, and not as a request to provide the proof. If so, then yes, provided it is actually true ;-)
By the way, it would be really tantalizing if somebody would prove P=NP but in a non-constructive way, i.e. proving that all NP problems can be solved in polynomial time but providing absolutely no clue about *how* to achieve this...
I've not gone anywhere near the problem myself, but intuitively, the proof almost has to be nonconstructive. A constructive proof would mean that given any validation algorithm, you construct an algorithm of proof with the same (or better) O(n) characteristic.
This feels---preposterous.
... are probably just a theoretical physicist, where setting c=1 is entirely legitimate and frequently the most convenient thing to do.
This is distinct from various preliminary "back of the envelope" scrawlings where you might also have 1=c=hbar=pi=e=2=-1 :-)
"I had to prove that 1≠2"
While this is understandably startling for the layman, a mathematician would just immediately propose the opposite assumption ("1=2") and drive it straight into the nearest impossibility using only rigorous logic on the way. Done. Not that I have any idea what that might be, mind, but hey I'm not a mathematician...
"...While this is understandably startling for the layman, a mathematician would just immediately propose the opposite assumption ("1=2") and drive it straight into the nearest impossibility using only rigorous logic on the way...."
Bertrand Russell held a lecture once, where he said:
-If you assume one single errornous piece as a fact, then you can prove anything!
-I dont belive you. If you assume that 1=2, can you prove that... you are the pope??
-The proof is trivial. I and the pope are 2 different persons, which means we are 1 person by (the faulty) assumption. Hence, I am the pope.
The Clay Mathematics Institute is offering $1m in prize money for solutions to these problems.
The Clay Mathematics Institute is silly because if some has the solution (as long as it is constructive) he would be RAKING it in and probably take over the very living brains of the Clay Institute Members by midnight.
Say Brain, what do you want to do tonight?
The same we do every day Pinky: Try to prove P=NP!
ARF!
I don't think "proving that P != NP" would let anyone "rake it in". Everyone already assumes that's the case, so proving it is just a formality - a big intellectual challenge, but in practical terms it would make sod all difference to anything.
Now, if you could prove the opposite, that would be something else entirely.
> Now, if you could prove the opposite, that would be something else entirely.
Yep, that would be the premise of the film Sneakers, starring Robert Redford as a pen tester, and James Earl Jones as head of a three-letter agency. Supporting cast includes Ben Kingsley, River Pheonix, Mary McDonnell, Dan Akroyd and Sidney Poitier.
Surely they meant to say "Analysing via means of real-time driven big-data machine learning utilising state of the art infrastructure of our sponsors at Azure - providers of the most stable and scalable cloud computing infrastructure for unprecedented super-computing tasks for tomorrows demanding research effort..."
(of fuck it, I'm only on my second coffee and couldn't continue in fears of throwing up. I'm so sorry mum. I couldn't help. It's the commies fault!)
Where is that bottle of scotch?
As in is the question is N<> NP decidable?
I've been presuming that it has been proven that an answer is possible, even if we don't know what it is.
But what if it isn't?
I know this sounds like one of those "how many angels can dance on the head of a pin" questions but if it really is undecidable (as the halting problem is) then we seem kind of f**ked.
And I'm not enough of a logician to know if it is.
We know that there are true statements that cannot be proven. IMHO, this is in the class of problems which might, just might, actually be unprovable. So yes, either P == NP, or P != NP, but we might also get a proof that we cannot prove P == NP (or not) with standard set theory. Oddly enough, the latter might be provable with standard set theory....
Easy to misunderstand issue, because _on face value_ the way it's stated in the article is flat out ridiculous (_of course_ there are problems that are hard to solve but easy to check, we have a list of examples, with factoring to primes right on the top); that said, even in that form, the question is actually perfectly valid, asking whether there really is no easy way to solve such problems, ever, or whether it's only hard because we have no idea how to do it easily, yet.
If it weren't for the smallness of Mr Fermat's margins we wouldn't have a whole bunch of number theory, not least Galois Theory - even though those discoveries were obtained while failing to prove the theorem.
I wonder what advances have come from all the failed attempts to prove P=NP, or otherwise.
There are of course tons of crackpots who come up with their "proofs" that P is or is not NP, but this was a real Comp.Sci. professor from a respectable university. Obviously the odds where still that there was a mistake, but I think it was justified to take notice this time.
This post has been deleted by its author
For the P vs. NP problem, almost all researchers believe P = NP. And this problem is still unsolved. If P = NP, this bias would be a significant loss. I submitted a paper claiming P = NP to STOC 2020 and was rejected with an only comment of “doubtful.” I rewrote it and opened it on a site, it achieved over 2500 accesses in only two days. It could exceed 100 accesses per hour. This access speed is a bit unusual, says a researcher in other fields. If you glance at my paper, you will see that I am seriously researching.
https://www.researchgate.net/publication/339627657_Extract_maximum_independent_set_using_eigenvalue_relation?channel=doi&linkId=5e5d20efa6fdccbeba12d7c6&showFulltext=true