Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

P ≠ NP

scribd.com

Post reply on HN
Print view View original

61–70 of 233 posts

Re: P ≠ NP

#61

Post by nkassis »

ramidarigaz wrote: post #30
carnevalem wrote: post #26

Earlier quoted context omitted.

I hear this statement frequently when P = NP is discussed, but as someone not involved in computer science I have a hard time understanding it. Could you explain what some of those consequences be? Does P = NP really need to be proved to achieve those practical consequences? Can't it just be assumed to be true and then see what the result is?

If P = NP were proved to be true, it would tell us that there are solutions to a certain class of problems. Assuming it's true doesn't give us those solutions. Wikipedia should answer most of your questions regarding the consequences: http://en.wikipedia.org/wiki/P_%3D_NP#Consequences_of_proof

To be a little more precise, proving P=NP would mean that there are algorithms to solve those problems that take polynomial time (can be calculated with a polynomial).

NP problems can be solved, it's just slow (think brute force method, running through all the possibilities).

Re: P ≠ NP

#62

Post by miloshh »

randomwalker wrote: post #41

Several points on the question of whether the proof is likely to be correct: * As far as I know this paper wasn't circulated for informal peer review before being made public; I heard no talk on the grapevine. (Edit: apparently it was circulated and someone other than the author made it public.) * Therefore a proper assessment is going to take a while. Until then we can only speculate :-) * While the crank attempts a…

Very good summary.

Though I was just reading the synopsis, and the statistical physics part seems to be proven: "The 1RSB ansatz of statistical mechanics says that the space of solutions of random k-SAT shatters into exponentially many clusters of solutions when the clause density is sufficiently high. This phase is called 1dRSB (1- Step Dynamic Replica Symmetry Breaking) and was conjectured by physicists as part of the 1RSB ansatz. It has since been rigorously proved for high values of k. It demonstrates the properties of high correlation between large sets of variables that we will need."

I did not dig into the references yet, though.

Re: P ≠ NP

#63

Post by pavs »

endlessvoid94 wrote: post #51
wingo wrote: post #36

Earlier quoted context omitted.

This is not the point.

Sure it is. Scribd has succeeded in going from "the worst pdf viewer on the web" to something that's perfectly usable using HTML5.

2 things.

- The html5 transformation is not instant. Everyone gets the Flash reader till the HTML5 version gets ready. Which can be anywhere between minutes to hours (I don't know the avg time).

- The HTML5 version or the Flash is worse than a plain old PDF viewer. Have you used the Integrated PDF viewer in Chrome lately? PDF under chrome makes reading PDF fun again, its the fastest/smoothest PDF viewer I have ever used

Also in order for me to download the PDF version I have to either register or sign in with my facebook account? What nonsense is that?

Re: P ≠ NP

#64

Post by Locke1689 »

WildUtah wrote: post #54

Everyone has been suspecting or assuming that P is a strict subset of NP for decades. Still, every time someone proposes a serious attempt at proving it, it's front page news and smart people will have to comb over the argument for months to have confidence that it's right. The opposite proposition -- that P is equal to NP -- is widely doubted. But if there were a proof that P and NP were equal, anyone with a good da…

Actually that's only possible for one case -- a proof by counterexample. If, hypothetically, one were to prove that P=NP and only that an algorithm exists to solve NP-complete problems in P time, then that might be verifiable. However, even if that were the case, what if it turns out that the P-time algorithm complexity were O(n^100,000). That would be P-time, but not easily run for large NP-complete problems.

Re: P ≠ NP

#65

Post by Ramfjord »

WildUtah wrote: post #54

Everyone has been suspecting or assuming that P is a strict subset of NP for decades. Still, every time someone proposes a serious attempt at proving it, it's front page news and smart people will have to comb over the argument for months to have confidence that it's right. The opposite proposition -- that P is equal to NP -- is widely doubted. But if there were a proof that P and NP were equal, anyone with a good da…

P is a strict subset of NP. If you can solve the problem in polynomial time, then you can verify a solution simply by generating it.

Re: P ≠ NP

#66

Post by Groxx »

ynniv wrote: post #16
dalton wrote: post #4

WOW. Assuming this isn't a hoax, and the proof holds up, this is front-page news kind of big deal. As I recall, this has way more real-world practical usage than the Fermats Last Theorem proof. Read the "Consequences of Proof" section in the Wikipedia article here: http://en.wikipedia.org/wiki/P_versus_NP_problem [edit] The responses below are correct. Proving P=NP means the world gets turned upside down. P != NP is…

a) Complicated academic proofs take (and should take) months if not years to verify, and will only be "front-page news" after verification. This is hardly the first unverified proof of the [edit: possible (in)]equality of P and NP. b) The practical consequences of P=NP are immense. The practical consequences of P≠NP are that we can stop looking for computational unicorns and fairies. We have for some time thought tha…

I doubt it'll impact the unicorns-and-fairies searches significantly. Most people already work under the assumption that P≠NP.

Similarly, most people believe the world is round, and we go around the Sun. This hasn't prevented serious flat-Earthers nor geocentrists from existing.

Re: P ≠ NP

#67

Post by moultano »

lkozma wrote: post #40

I 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…

The general feeling is that creativity is hard, and even exponentially hard. When people try to do things creatively they feel like they aren't doing that much better than trying all possibilities and rejecting the ones that don't work.

If someone proved P=NP then unless we're mistaken about how hard we have to work to think creatively, it's likely that computers will end up being better than us at it, using this algorithm that I suspect would be difficult to backport to our brains. :)

Then again, it's possible that skilled practitioners of any creative field have stumbled across this polynomial time algorithm and don't know it, but that seems unlikely.

Re: P ≠ NP

#68

Post by leif »

zacs wrote: post #37

The paper's origin was that the author mailed a copy for review to some very high-level folks in the field (Cook, Mazirani, Sipser, etc). Here's the mail: Date: Fri, 6 Aug 2010 21:28:39 +0000 Subject: Proof announcement: P is not equal to NP Dear Fellow Researchers, I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts. The proof required the piecing together of principl…

Somewhere, deep in a dark corner of my heart, I hope and pray that this paper is correct, just so we can keep and revere the immortal words "I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts."

Re: P ≠ NP

#69

Post by Groxx »

mojuba wrote: post #50
lkozma wrote: post #40

I 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…

While I agree P != NP doesn't say anything about human creativity, but the reason it can't be automated is, I think, different: creativity is closely tied to libido and biological evolution, which in turn can't be simulated in machines in full.

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 motivated to be creative, so we are. Programs can be similarly guided towards ends we desire; perhaps the most direct analogy is genetic programming, where you determine which "breed" by their "fitness" value.

Re: P ≠ NP

#70

Post by [deleted] »

emmett wrote: post #29
tzs wrote: post #3

102 pages via one of the most annoying PDF readers on the planet? No thanks. There are good, free, PDF readers for every major operating system and for every major mobile device. I wish people would just link directly to PDFs.

Have you tried Scribd since they've transitioned to HTML 5? I now find it quite usable.

[deleted]
Post reply on HN