Comment by 1arity | Hacker News Reader

Comment by 1arity | Hacker News Reader

Parent Full thread

Because believing P != NP means, and is frequently invoked as a justification that : 1) we no longer have to keep looking for a P time algo, and 2) ah, that's why we couldn't solve that -- because we proved it is in NP, and P isn't equal to that, so we can chalk our failure to solve it up to that.

P == NP is leaving the possibility open, which, by absence of a proof to the contrary __is__ open, that we __can__ find an algorithm. That is not defeatist.

That is let's keep going. Let's make it.

What you believe is your choice. To me it seems a waste of good brains to see so much CS talent giving themselves an easy out like this. I know where I stand and I'll keep working on the things I care about.

People can choose to be part of the future, or left in the dust of those who walk ahead.

My view is -- all those really hard unsolved problems? That's where everyone should be focussing. Anything else is just nibbling around the edges, it's just a cowardly hedge. A waste. The incentives have become toxic to the creation of brave innovation. People are satisfied with too little.

consider a world in which P equals NP.

What does this mean? All internet crypto could break, almost immediately if a valid a solution were found. What does this do to society?

A philosophical class on skeptisim, or a class on software security - they both lead to the same conclusion, that the outside world is a potentially terrifying place. Identities can give rise to trust in something out side of you - but it's impossible to form identities without a "one way" computational mechanism like P != NP. Our ability to say "You know me by my words; you can recognize my language, but cant speak it yourself" - that doesn't work any more if P = NP. The ability to say "yes, that's MarkPNeyer saying that" is the same as the ability to speak with my voice.

Now consider a world in which P does not equal NP.

- it suggests that a single expert is not as powerful as large groups; a single person acting alone is like a single turing machine. A quantum computer is sort of like society - everyone tries their own way, and if someone finds a solution that works, it is made obvious to everyone else through their success.

- it provides a meaningful basis for identity. Someone can publish cryptogrpahically signed statements attesting to a believe, and we can trust that it's the same person (or group of people) operating behind that identity, becuase of the meanignful difference between verifying a truth (this is the same person who posted these keys) and finding a solution (find the private key which leads to posting these two things.)

Now, of course the "world I want to live in" does't directly suggest anything one way or the other - I'm just hoping you can stop seeing "P != NP" as being defeatist - if anything, it's a wonderful result, from a philosophical perspective, because it implies a world rich, full of diversity, with meaningful notions of identity.

If P = NP, the polynomial time hierarchy collapses - and there's a good chance society does as well.

Societies that fragile, will collapse irrespective of mathematics. Besides, the fact that current tools rely on the != conjecture doesn't require future tools to do so.

> Besides, the fact that current tools rely on the != conjecture doesn't require future tools to do so.

Depends on what kind of tools you're talking about. For instance, if P==NP then there can be no such thing as a secure digital signature algorithm; anybody who can efficiently verify a signature can also forge one. (Making the usual simplification that "efficient" == "polynomial-time", that is.)

Is there a reason to believe that no e.g. PSPACE algorithm would be suitable for signatures? (Even assuming that such are not practical now, can we say they wouldn't eventually be practical in a P=NP world?)

I don't really see why society collapses. If P=NP it means that we can optimally solve problems that we currently can't solve. If P=NP, you don't need the market to find the solution that works, you just compute it.

>ah, that's why we couldn't solve that -- because we proved it is in NP, and P isn't equal to that, so we can chalk our failure to solve it up to that.

Except that line of reasoning is completely incorrect -- both in its understanding of the problem, and in its understanding of the current state of the field. For one, most "interesting" problems are in NP, not the least of reasons being P is undeniably a subset of NP. Here's a nice Venn-diagram-like thing on wikipedia:

https://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard....

So if you prove your solution is NP, you don't get to say "Whelp, it's impossible!" and move on. That would be like saying "We proved that you could build this machine if we had a perpetual motion engine, and those are probably impossible, so the machine can't be built." If, on the other hand, you prove that your machine could be used to build a "perpetual motion engine" (i.e. a poly-time solution to the new problem could be used to construct a poly-time solution to an NP-complete problem), then that might be a good time to admit it's almost certainly impossible to build it. But again, that's not where the field lets it rest.

NP-complete problems have very direct applications to many, many real world problems we try to solve. The state of the art in these solutions is not "It will never be polynomial time, so we don't try." Research papers are constantly churning out new, faster algorithms for NP-complete problems -- they're just not poly-time algorithms. For example, k-sat is the most textbook example of an NP-complete problem, and there is an annual competition regarding the latest algorithms for solving it: http://www.satcompetition.org/ In fact, working on this stuff isn't exactly the smallest field within CS, and a novel solution yielding better performance does very well to an academic reputation, and there are definitely people trying.

So rest assured, in the unlikely event that some new techniques arise that allow the creation of poly-time solutions to NP-complete problems, they will not go unnoticed. But thanks for calling us cowards.

Reply on news.ycombinator.com