What to do? Read paper or hit next months deadline...
P ≠ NP
211–220 of 233 posts
Re: P ≠ NP
#212Earlier quoted context omitted.
It's a leaked PDF of an unverified proof which has yet to appear in any mainstream news source and is relevant, probably, to no one but computer scientists. So it's not even remotely surprising that it has not yet appeared on Google News. I have no idea what part of this you think is sad.
This result is much more relevant than either Perelman's proof of the Poincare Conjuncture or Wiles' proof or Fermat's Conjuncture, both of which got huge coverage in the mainstream media. If you think this is relevant to "no one but computer scientists" you are naive about the ramifications of the result. The proof is unverified but most qualified sources say it is one of the best efforts in many years, it could eve…
The thing is, we can't talk about any result yet. So far, we only have a paper which didn't even underwent peer-review. I'm sure it will get enormous media coverage, but not sooner than it gets published.
Re: P ≠ NP
#213Earlier quoted context omitted.
I'd argue that if (assuming it's true that) creativity stems from libido and biological evolution, it's been because there are evolutionary gains for creative individuals. The first person to throw a rock at a tree to knock down fruit got more food, for instance. The most complicated clothing (/nest/dance) gets the most mates. All of which means it's purely a motivating force , not a requirement . We've been motivate…
What I actually meant was what we create rather than why .
Exactly my point: what we create is incredibly tightly tied to why we create, especially if you're looking at it from an evolutionary standpoint. I wouldn't call it an isomorphic relationship, but darn close.
You also have to consider that our creativity has been created by the equivalent of billions of the individuals with more computational power than the most powerful computer in the world right now, running for thousands of years of recorded history. Absolutely nothing we have done with computers approaches this, especially when you consider just how unexplored computer A.I. really is. If we call it ten orders of magnitude more "power", we're making a phenomenally conservative estimate. What could you do with a computer over a billion times more powerful than everything that Google owns?
I'd say our less-than-10-billionth computational efforts have in fact created a couple creative things. Which puts them about on par.
Re: P ≠ NP
#214Earlier quoted context omitted.
You must read it in context. What it says is that if P == NP then the implications are profound for applications such as cryptography and on the general question of whether human creativity can be automated. You can see why P == NP would have profound implications for crypto: many of our widely used techniques would turn out to, um, be easy to crack. I believe the intent regarding human creativity is that humans ofte…
Lets assume that P==NP, why assume that we would be able to find algorithms to easily crack crypto? Let me put it another way, lets say that we finally discover that it is possible to time travel to the past. However, the energy needed to travel back int time is the equivalent of a million Suns because that is the amount of energy needed to warp space enough so that time will reverse itself. And we found proof of thi…
NPC algorithms are roughly equivalent, so a P solution to one is a P solution to all. So, assuming the proof would be somewhat constructive, that would give you a P solution.
But, RSA (and probably other) cryptosystems aren't even thought to be NPC to solve... so they're probably unaffected. So, I guess it depends on the implementation details of the cryptosystem. Probably it wouldn't render them wide open, but it might make previously good keys far weaker, and mean that much longer must be spent on encryption for it to be safe (rather than now where a safe key can be decoded almost instantly on an embedded platform).
Re: P ≠ NP
#215Earlier quoted context omitted.
That's not a very good example - square matrix multiplication is O(n^1.5) (where n is the input size) and extremely fast in practice. (Though, as you say, there could still be an O(n) algorithm - this is not known). What I said is true even for linear programming (a P-complete problem) - it has polynomial and efficient algorithms - though the latter are actually not polynomial in the worst case. :)
Can you give a reference for a matrix multiplication algorithm which is O(n^1.5) ? thanks.
Note that I defined n as the input size...
Re: P ≠ NP
#216I think this is getting unwanted publicity. The author never released the proof in public or made any announcement. He only sent it to his expert friends so that they can point out potential flaws. May be this needs more research and putting him in spotlight is not helping anything.
Actually I think a leak is more helpful than either the author himself releasing the proof publicly or keeping everything under wraps.
Especially since the cold fusion thing[1], researchers have been loath to publicly announce revolutionary findings lest the findings fail to pan out. Researchers don't want to be known as publicity-seeking cranks, they want to be known as earnest and honest academics, which I suspect entails playing to the in-crowd and letting the system work[2]--the system being to talk to your colleagues before hand, release everything through peer-reviewed journals, and if everything passes muster, you've eliminated any risks to your reputation while achieving renown as the guy who proved P != NP.
On the other hand, having the proof publicly available to anyone who can understand it can massively parallelize the process of having it verified, or having errors found and potentially corrected. Meanwhile, the researcher's reputation is maintained, because he did the right thing, and if any errors are found he'll be judged to have acted prudently and conservatively in advance of having his findings reviewed.
[1] Fleischmann and Pons publicly claimed to have discovered a means to induce nuclear fusion at room temperature in 1989, but their results couldn't be replicated.
[2] And the system does work--this is no criticism.
Re: P ≠ NP
#217Earlier quoted context omitted.
Agree fully. Also worth considering if this proof turns out to be correct, is that he will probably have employment contracts and speaker deals dwarfing that $1M quite soon.
Money is the last thing to care about if you solve P ?= NP. Humanity will remember you in same league as Turing Pythagoras Gauss and others.
You can't eat prestige. Nor find joy in a life of isolation. Look at Rembrandt's philosopher if you want the true picture of the life of the mind.
How history remembers you only matters after you're dead. Can you really tell someone to live a life of solitary confinement? The isolating parts of academia honestly suck. But everyone convinces themselves that academia is so great, in part because so many have gone before, suffering, down the same path.
Look at all the theoretical physicists and mathematicians. Do you think these people are HAPPY? Remember, if you leave math you are "dead." It's about sacrifice, not about your health or happiness as a human being.
The best part of academia is the collaboration, the social aspects. As for the environment, it could definitely be renovated to make accommodation for humanity. Obviously that will never happen. So there needs to be big CAUTION signs posted up whenever someone lauds the greatness of academia, saying it is not all fun and games, lots of people spend decades locked in offices hunched over pieces of paper.
Re: P ≠ NP
#218I skimmed through the synopsis but this philosophical statement baffles me (although obviously it is unrelated to the validity or invalidity of the proof): "The implications of [P ?= NP] on the general philosophical question of [..] whether human creativity can be automated, would be profound." How so? If P!=NP, that is obeyed by the brain as much as by computers and whatever trick our brains does to be creative desp…
Wikipedia on P ?= NP: In essence, the question P = NP? asks: if 'yes'-answers to a 'yes'-or-'no'-question can be verified "quickly" can the answers themselves also be computed "quickly"? Scott Aaronson: If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the so…
The problem with these grandiose statements is that they forget the word formal. You have to be searching on a space that's formally defined to make optimization=verification if P=NP. When we do art and creativity, the space is not formally defined a priori. Hell, even theorem-proving isn't. Look at the breakthroughs in mathematics and most of them, a really large majority, came from applying some new ideas or operations (e.g., ricci flows) to problems that all others simply could not see as applicable. There are no "profound philosophical implications" if P=NP (which I doubt) other than our universe lets us have polynomially bounded algorithms for a huge cluster of problems.
Re: P ≠ NP
#219Earlier quoted context omitted.
Wrong area for a Nobel prize, the prize areas are physics, chemistry, physiology/medicine, literature, and peace. There is also a prize in economics given at the same time.
Perhaps he could steal the Economics "Nobel" prize, like lots of other mathematicians have done. There was a paper about how recognizing bad securities is a NP hard problem a while ago. So this is applicable. (Tongue-in-cheek.)
Re: P ≠ NP
#220P = NP if and only if N = 1 or P = 0
Beat you to it! http://twitter.com/peterc/status/20667523417 I didn't post it here because I realized it's a joke most people won't get and those who do get it won't find it funny ;-) This joke could even be a Reddit vs HN shibboleth as I just saw it made there too and it's being voted up.
P!=NP if and only if P=1 and N=1.