I think "a large number of interesting solutions" is a bit of an understatement. It would mean that perfect unsupervised learning would be possible which would probably quickly usher in strong AI. I don't think we can even imagine what it would do to life on this planet if we had a reduction proof showing P = NP.
This is technically possible, but probably very unlikely. No natural problems are known which have a non-trivial lower bound of more than (I believe) \Omega(n^2). It seems that problems in higher polynomial classes are either very rare or we have yet to consider fields of math which would produce them.
Another thing to consider is that we still don't know whether factoring, discrete logarithms, etc are even in NP in the first place
Yes this is quite easily proven. Problems in NP can be efficiently verified and it is very easy to verify, if I give you two factors p and q, whether they multiply to a number n.
Proving P=NP would mean a P solution to an NP problem was theoretically possible, but it wouldn't necessarily help you find one.
Barring some very strange proof that would be fundamentally different from the way we currently know how to prove things in complexity that is exactly what it would mean. The proof would likely take the form of a reduction of some NP-complete problem to some problem in P, which would then, via a series of transformations, allow for all problems in NP to be solved in P time.
Everyone is arguing with your second point but I will actually take issue with the first:
The expected answer means we will have cryptographic security available indefinitely. We may have to keep switching algorithms, but in principle there will always be an algorithm out there that can't be quickly bypassed.
That is actually not true. There is a very famous paper by Russell Impagliazzo titled A Personal View of Average-Case Complexity where he outlines five possible "worlds" we could be living in, hinged on the answer to some unknown questions. One of these is whether P = NP, but another is about average-case hardness (because P and NP are only defined for worst-case problems).
The only world that is now no longer possible, if this new result is correct, is the first world Algorithmica where P = NP and every problem is essentially easy to solve. There are four other worlds that we could still be in, and I highly encourage you to read the paper to check them out, but one important point is that we could be in a situation where P != NP but the hard instances of problems are actually, in themselves, hard to find, i.e. average case problems are easy.
This would preclude cryptography as we know it because it would be just as hard to encrypt something as it would be to break it. You could still encrypt if you are the government and you have billions of dollars of computers but it becomes effectively an arms race between attackers and defenders, and whoever spends more processing power wins.
There is also the possibility that P != NP but one-way functions do not exist. That is, every function which can be efficiently computed in a forward direction can also be efficiently computed in the reverse direction. This would be the worst possibility because we would gain no new scientific advancement from fast algorithms to solve things like protein folding, circuit design, etc. and cryptography would also be impossible.
If they actually threatened violence against him, yeah I am fine with them being arrested. What I saw in the video was mostly them saying "go home terrorist" and "fuck you" a lot. Again, I am fine with equal treatment for both sides, you are the one that is not. You pretend that "fuck you" is the same as "all jews should die and here is how it should be done." You are the one equating yelling in someone's face with running them over with a car. One is not like the other.
What liberals brag about actually doing is far more scary than what some fringe group is accused of advocating.
Pretty sure no liberals have actually committed genocide, but there are a scary amount of fringe groups advocating it. You need to get some perspective and realize that taking down a website is not even close to murdering someone.
Looks pretty peaceful to me. Nobody ran him over with a car. In fact, he was completely unharmed. Isn't this the kind of protest you spend hours on here defending?
Jesus fucking christ AC... this is the most ridiculous comment of all. In that poem the people "coming for you" WERE the fucking Nazis, and coming for you didn't mean taking down your website, it meant a concentration camp. Just fuck right off.
Are you not familiar with the idea of propaganda? Just because people are nazis doesn't mean they are stupid. Some are actually evil, and very good at propaganda. How do you think WWII happened in the first place? All of Germany were idiots? We need to stop that from happening again.
As I already said, there is an even closer example of Germany where it is illegal to be a nazi or use nazi iconography and they seem to be doing just fine. Nobody over there accusing people of being nazis left and right.
Slashdot Mirror
I think "a large number of interesting solutions" is a bit of an understatement. It would mean that perfect unsupervised learning would be possible which would probably quickly usher in strong AI. I don't think we can even imagine what it would do to life on this planet if we had a reduction proof showing P = NP.
This is technically possible, but probably very unlikely. No natural problems are known which have a non-trivial lower bound of more than (I believe) \Omega(n^2). It seems that problems in higher polynomial classes are either very rare or we have yet to consider fields of math which would produce them.
Another thing to consider is that we still don't know whether factoring, discrete logarithms, etc are even in NP in the first place
Yes this is quite easily proven. Problems in NP can be efficiently verified and it is very easy to verify, if I give you two factors p and q, whether they multiply to a number n.
Proving P=NP would mean a P solution to an NP problem was theoretically possible, but it wouldn't necessarily help you find one.
Barring some very strange proof that would be fundamentally different from the way we currently know how to prove things in complexity that is exactly what it would mean. The proof would likely take the form of a reduction of some NP-complete problem to some problem in P, which would then, via a series of transformations, allow for all problems in NP to be solved in P time.
The expected answer means we will have cryptographic security available indefinitely. We may have to keep switching algorithms, but in principle there will always be an algorithm out there that can't be quickly bypassed.
That is actually not true. There is a very famous paper by Russell Impagliazzo titled A Personal View of Average-Case Complexity where he outlines five possible "worlds" we could be living in, hinged on the answer to some unknown questions. One of these is whether P = NP, but another is about average-case hardness (because P and NP are only defined for worst-case problems).
The only world that is now no longer possible, if this new result is correct, is the first world Algorithmica where P = NP and every problem is essentially easy to solve. There are four other worlds that we could still be in, and I highly encourage you to read the paper to check them out, but one important point is that we could be in a situation where P != NP but the hard instances of problems are actually, in themselves, hard to find, i.e. average case problems are easy.
This would preclude cryptography as we know it because it would be just as hard to encrypt something as it would be to break it. You could still encrypt if you are the government and you have billions of dollars of computers but it becomes effectively an arms race between attackers and defenders, and whoever spends more processing power wins.
There is also the possibility that P != NP but one-way functions do not exist. That is, every function which can be efficiently computed in a forward direction can also be efficiently computed in the reverse direction. This would be the worst possibility because we would gain no new scientific advancement from fast algorithms to solve things like protein folding, circuit design, etc. and cryptography would also be impossible.
We're talking about the US here but thanks for trying.
Yep I don't agree with that, sounds pretty dumb. Next?
If they actually threatened violence against him, yeah I am fine with them being arrested. What I saw in the video was mostly them saying "go home terrorist" and "fuck you" a lot. Again, I am fine with equal treatment for both sides, you are the one that is not. You pretend that "fuck you" is the same as "all jews should die and here is how it should be done." You are the one equating yelling in someone's face with running them over with a car. One is not like the other.
What liberals brag about actually doing is far more scary than what some fringe group is accused of advocating.
Pretty sure no liberals have actually committed genocide, but there are a scary amount of fringe groups advocating it. You need to get some perspective and realize that taking down a website is not even close to murdering someone.
Looks pretty peaceful to me. Nobody ran him over with a car. In fact, he was completely unharmed. Isn't this the kind of protest you spend hours on here defending?
Jesus fucking christ AC... this is the most ridiculous comment of all. In that poem the people "coming for you" WERE the fucking Nazis, and coming for you didn't mean taking down your website, it meant a concentration camp. Just fuck right off.
Are you not familiar with the idea of propaganda? Just because people are nazis doesn't mean they are stupid. Some are actually evil, and very good at propaganda. How do you think WWII happened in the first place? All of Germany were idiots? We need to stop that from happening again.
https://yourlogicalfallacyis.c...
That's not what a common carrier is. Please stop misusing that term.
The people claiming to be nazis and running around with swastikas on everything. They are definitely the fascists. They will say so if you ask them.
It was made a crime to identify as a nazi or use nazi iconography in Germany, which it still is today. I think they have it right.
Cool story bro. Keep on justifying your cowardice.
If your political philosophy cannot withstand a little valid criticism
You just said that nazis have valid criticisms.
As I already said, there is an even closer example of Germany where it is illegal to be a nazi or use nazi iconography and they seem to be doing just fine. Nobody over there accusing people of being nazis left and right.
Oh look its AC adding nothing of value to anything. Keep on being a coward.
Ok that was actually funny lol
Why are you trying so hard to find some way of tallying up violence so that you can put nazis on the "right" side? Think about your life for a second.
Oh I see, you are not an idiot you are actually mentally ill. My bad, have a good day.
He literally yelled, "this is what liberalism gets you" when he stabbed a guy in the throat. He is on video saying that. Is that fake news?
Oh man kind of exactly like this https://www.youtube.com/watch?...