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

161–170 of 303 posts

Re: A Solution of the P versus NP Problem?

#161

Post by legulere »

zolthrowaway wrote: post #21
choxi wrote: post #14

What are the implications of solving the P versus NP problem? What practical effects would that have? Not trying to belittle the problem, just curious as an outsider.

The most interesting thing is if P=NP. If that's the case, that means that there is an algorithm that can solve any NP problem in polynomial time. This means that things like crypto would be able to be cracked in polynomial time which presents a huge problem for security. We basically operate under the assumption that P!=NP currently. Validation that this is true doesn't really change much. I can't speak to how this…

Would it present a problem for cryptography though? Quadratic algorithms are seen as already slow, cubic algorithms as unbearable garbage you best try to avoid if your data size is not tiny. And this completely ignores constant factors that can play a big role. Homomorphic encryption for instance fails to be usable just on a huge constant factor.

Re: A Solution of the P versus NP Problem?

#162

Post by valine »

DominikPeters wrote: post #90

A list of 116 previous "solutions" to the P versus NP problem: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

After skimming its interesting that the majority of the proofs in your list claim P equals NP. I would have guessed it would be more common for proofs to claim the opposite because P != NP makes sense intuitively. That being said it would certainly be more exciting if P did equal NP.

Re: A Solution of the P versus NP Problem?

#163

Post by Gehinnn »

vanjoe wrote: post #56
zolthrowaway wrote: post #21

Earlier quoted context omitted.

The most interesting thing is if P=NP. If that's the case, that means that there is an algorithm that can solve any NP problem in polynomial time. This means that things like crypto would be able to be cracked in polynomial time which presents a huge problem for security. We basically operate under the assumption that P!=NP currently. Validation that this is true doesn't really change much. I can't speak to how this…

I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.

Actually, we already know an algorithm that solves an NP complete problem in polynomial time iff P = NP. We can just enumerate all programs and ask them to generate witnesses. As we can decide whether a witness is valid and there is a program that always outputs a valid witness if P=NP, we can find that program within finite steps and the algorithm is correct.

Re: A Solution of the P versus NP Problem?

#164

Post by monochromatic »

mathperson wrote: post #151
monochromatic wrote: post #136

Earlier quoted context omitted.

Not at all. But bringing him up in an unrelated post on a technical blog just screams "virtue signaling" to me.

I mean he also pokes fun at his children, himself, and posted a rap video about theoretical computer science on his blog. His blog is not exactly the Annals here... I think he is more than welcome to write about whatever he damn pleases and if you disagree you are more than welcome to argue in his comment sections (and more than likely lose)

Of course he's welcome to write about whatever he likes. It's his blog.

But I'm welcome to roll my eyes at it.

Re: A Solution of the P versus NP Problem?

#165

Post by monochromatic »

kybernetikos wrote: post #142
monochromatic wrote: post #136

Earlier quoted context omitted.

Not at all. But bringing him up in an unrelated post on a technical blog just screams "virtue signaling" to me.

When you feel strongly about something and write about it, you aren't virtue signalling, you're expressing your view. If you have any reason to take the rather uncharitable stance that his views on Trump are inauthentic, then post them, otherwise it's better just to assume that people who say things you disagree with actually think those things rather than are just saying them to look good. Accusing others of "virtue…

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

Re: A Solution of the P versus NP Problem?

#166

Post by mbrubeck »

valine wrote: post #162
DominikPeters wrote: post #90

A list of 116 previous "solutions" to the P versus NP problem: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

After skimming its interesting that the majority of the proofs in your list claim P equals NP. I would have guessed it would be more common for proofs to claim the opposite because P != NP makes sense intuitively. That being said it would certainly be more exciting if P did equal NP.

A simple but wrong proof of "P = NP" is easier to write in some ways, since you "just" need to provide a single algorithm for one NP-hard problem, and show that it runs in polynomial time. It looks like many or most of the proof attempts in that list take this form.

A plausible proof of "P != NP" won't be quite as simple to express, since it needs to prove that all such algorithms do not run in polynomial time.

Re: A Solution of the P versus NP Problem?

#167

Post by abecedarius »

1ris wrote: post #146
__s wrote: post #138

Earlier quoted context omitted.

Hence why Scott explicitly takes time to address that there will surely be outliers on both ends

I just wanted to point out that's is not a theoretical possibility, but actual ground breaking work did look sketchy as hell. The "The nice thing about math is that sooner or later the truth comes out" bothers me. The knowlege in Archimedes palimpsest was lost so long the eventually doesn't seem to be much comfort.

Grassman was another more recent example, though obviously we can't now find recent examples that will lie dormant for millennia...

Re: A Solution of the P versus NP Problem?

#168

Post by mathperson »

monochromatic wrote: post #164
mathperson wrote: post #151

Earlier quoted context omitted.

I mean he also pokes fun at his children, himself, and posted a rap video about theoretical computer science on his blog. His blog is not exactly the Annals here... I think he is more than welcome to write about whatever he damn pleases and if you disagree you are more than welcome to argue in his comment sections (and more than likely lose)

Of course he's welcome to write about whatever he likes. It's his blog. But I'm welcome to roll my eyes at it.

I'm rolling my eyes at your eye rolling! How deep can we go?!

Re: A Solution of the P versus NP Problem?

#169

Post by hug »

monochromatic wrote: post #136
Analemma_ wrote: post #85

Earlier quoted context omitted.

Are you one of those people who equates any mention whatsoever of Trump as "being needlessly political"?

Not at all. But bringing him up in an unrelated post on a technical blog just screams "virtue signaling" to me.

In what world is Scott Aaronson, a professor whose primary research area is computational complexity, unrelated to a P=NP solution?

Re: A Solution of the P versus NP Problem?

#170

Post by irundebian »

choxi wrote: post #14

What are the implications of solving the P versus NP problem? What practical effects would that have? Not trying to belittle the problem, just curious as an outsider.

Some cryptographic implications on solving the P vs. NP problem or proofing some other stuff on average case complexity: https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf
Post reply on HN