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

A Solution of the P versus NP Problem?

arxiv.org

Post reply on HN
Print view View original

281–290 of 303 posts

Re: A Solution of the P versus NP Problem?

#281

Post by CarolineW »

fazkan wrote: post #276
CarolineW wrote: post #259

Earlier quoted context omitted.

> From what I have read in the comments, there seems to be other papers which have also proved P!=NP. None of those papers have been accepted as correct, the problem remains open. There's a gazillion articles describing the context and importance, and I suggest you do a web search for something like "P vs NP and why it's important". Here's one: http://www.scottaaronson.com/blog/?p=459 HN discussion: https://news.ycom…

Thanks for the reply. Thats a great article. I have read a lot of articles like that, in fact was planning to write one myself. Just wanted to know more about the paper submitted i.e. what it proposes and the methodology adapted. I tried reading it but couldnt parse the data with all the jargons.

That's not the question you asked. If you want to know more about the context of this specific paper then you need to (a) wait for the people in the area to start writing explanations, or (b) ask more specific questions about specific terms.

A good place to start to get a sense of what's going on with this specific paper is this thread, but more particularly, the articles linked from it. One that I think is a great starting point is this one:

https://johncarlosbaez.wordpress.com/2017/08/15/norbert-blum...

But you should perhaps start by asking the question you actually want the answer to - it sounds like you didn't. So take a moment, do some reading, then come back with particular questions. They may already be answered, but before you did the outside reading you didn't realise. That's what happens to me.

Re: A Solution of the P versus NP Problem?

#282

Post by ouid »

jacquesm wrote: post #197
jl6 wrote: post #101

Earlier quoted context omitted.

And even though it may be hard to find the flaw, it will be easy to verify that it is a flaw.

This lines up perfectly with most software bugs. Hard to find, but once you have them easy to prove they are the cause of the problem. The difference is that in software bugs are usually fairly easy to fix, a math proof with a bug in it might not be fixable at all.

I think you missed the joke

Re: A Solution of the P versus NP Problem?

#283

Post by ajarmst »

I remain optimistic, but some potential holes are starting to show. Scott Aaronson: (http://www.scottaaronson.com/blog/?p=3389)

"To everyone who keeps asking me about the “new” P≠NP proof: I’d again bet $200,000 that the proof won’t stand, except that the last time I tried that, it didn’t achieve its purpose, which was to get people to stop asking me about it. So: the paper claims to give an exponential circuit lower bound for Andreev’s function, but that function as defined in Section 7 of the paper seems clearly to have a polynomial-size circuit, based on polynomial interpolation (thanks to Luca Trevisan for this observation). So I don’t see how this can possibly stand. Please just stop asking, and if the thing hasn’t been fully refuted by the end of the week, you can come back and tell me I was a closed-minded fool."

Re: A Solution of the P versus NP Problem?

#284

Post by ajarmst »

Tomte wrote: post #39

Scott Aaronson on "suppose someone sends you a complicated solution to a famous decades-old math problem, like P vs. NP. How can you decide, in ten minutes or less, whether the solution is worth reading?": http://www.scottaaronson.com/blog/?p=304

Aaronson has commented on this particular proof. He's, to say the least, skeptical, based on an observed polynomial circuit in section 7: http://www.scottaaronson.com/blog/?p=3389

Re: A Solution of the P versus NP Problem?

#285

Post by [deleted] »

ajarmst wrote: post #283

I remain optimistic, but some potential holes are starting to show. Scott Aaronson: ( http://www.scottaaronson.com/blog/?p=3389 ) "To everyone who keeps asking me about the “new” P≠NP proof: I’d again bet $200,000 that the proof won’t stand, except that the last time I tried that, it didn’t achieve its purpose, which was to get people to stop asking me about it. So: the paper claims to give an exponential circuit low…

[deleted]

Re: A Solution of the P versus NP Problem?

#287

Post by mihaild »

hexomancer wrote: post #232
mihaild wrote: post #127

Earlier quoted context omitted.

Decision version of TSP is NP-complete. Optimization version is Cook-reducible to decision version of TSP. And it problem is Cook-reducible to P-problem, then the problem is itself in P. (note that it's not true if you replace P with NP, for example)

Do you have a reference to a reputable source that proves the optimization version is cook-reducable to decision version?

I don't. (it's always hard to find reference for easy problems)

Re: A Solution of the P versus NP Problem?

#288

Post by kevincox »

PeterisP wrote: post #231
Ar-Curunir wrote: post #185

Earlier quoted context omitted.

Yes, it would. The adversary in cryptography is assumed to be worst-case evil; it'll do whatever it can to break your algorithm, as long as it's performing a polynomial amount of computation. Remember, you're not just fighting your friendly neighborhood hacker, but possibly entire nation-states.

You can easily have crypto that can't be broken with all the resources and time in the observable universe even if it's "just" polynomial with a sufficiently high coefficient.

Yes, but it becomes significantly more expensive. It might work but it is a huge difference in cost tradeoffs.

Re: A Solution of the P versus NP Problem?

#289

Post by dubstepjuggalo »

yters wrote: post #174

If p != np, then comp sci will lose much of its appeal. There is an underlying hope behind the field that p = np, otherwise most problems of interest are intractable, and programmers are no longer masters of the universe. This is probably why there is not a proof yet, since the truth is undesirable.

Uh... P ISN'T known to equal NP, but people seem to have a lot of fun using computers anyway.

Arguably, P=NP makes CS less fun, since an efficient "universal algorithm" could solve a vast class of problems in polynomial time, while P != NP means there's more room for programmer creativity making intractable problems tractable in special cases.

Re: A Solution of the P versus NP Problem?

#290

Post by monochromatic »

vecter wrote: post #252
monochromatic wrote: post #165

Earlier quoted context omitted.

I'm curious what I said that sounded to you like "his stated views on Trump aren't authentic."

https://en.wikipedia.org/wiki/Virtue_signalling Virtue signalling is the conspicuous expression of moral values done primarily with the intent of enhancing standing within a social group. I don't think Aaronson states his views on Trump with the hopes of increasing his social status. He does it because it's just what he feels and wants to express himself.

And which part of that definition has anything to do with the views being inauthentic?

I feel like I'm taking crazy pills here.

Post reply on HN