Does /g/ think P = NP?
>>51726535
Yes, as long as N=1.
>>51726554
At last, I truly see.
>implying many people here understand this
I think that probably not. But a lot of problems can use tricks and heuristics to come close to polynomial speed.
>>51726535
/g/ usually doesn't know anything about computation except writing simple programming examples like fizzbuzz.
While P ?= NP is one of the easiest to understand Problems, I doubt anyone here has a firm grasp of it.
I personally would be stoked if P = NP
if you could say np is p if p = np then universe = np
>>51726818
>come close to polynomial speed
Enjoy flipping burgers with that worse than average degree
Can someone Explain Like I'm Five what P = NP is supposed to be about?
Who gives a fuck?
>>51727243
>Can someone Explain Like I'm Five
>>>/reddit/
>>51727243
P: Polynomial, the class of problems for which a solution can be computed in polynomial time (on a classical computer, let's not get into quantum here). That is, the number of steps required to solve it grows like a polynomial (on the order n^x for input size n, for some finite x. A lot of problems are on the order of n^2, for example). These are the "easy" problems.
NP: Nondeterministic Polynomial: the class of problems for which we can decide the correctness of a solution in polynomial time. Finding that solution isn't necessarily possible in polynomial time. P is a part of NP, obviously. A lot of these have exponential time complexities, which gets horrible really quickly, we consider these to be "hard" problems.
>>51727394
(cont.)
If P=NP, then all problems in NP are also in P and can thus be solved "relatively easily" (a horrible polynomial runtime is still beter than exponential, if the input sizes get really big). If not, then there exist problems which can not be solved in polynomial time on a classical computer. Such problems are NP-complete, and we think there are quite a number of them.
The big argument against P=NP is that after so much research into NP-complete programs, no P-time algorithm has been found for a single one of them. It's not a great argument, but considering some of the NP problems are so simple, you'd think we'd have found a better algorithm by now if it existed.
If P=NP turns out to be true, there are a number of consequences. Cryptography often relies on certain problems being hard, if we can efficiently solve 3-SAT (a well known NP-complete problem), you can throw a lot of crypto in the trash. A lot of problems with nice real-world applications would also have a quick algorithm, which would actually be kind of nice.
>>51727243
Basically if P=NP, then encryption like 128-bit aes will be on suicide watch.
>>51727243
P would be problems that are easy such as arithmetic operations that can be solved in polynomial time.
NP would be harder problems like factoring larger numbers, and since the larger the number is; it takes an exponentially longer time to factor it rather than a polynomial amount.
>>51727740
this is an "idiot's guide to the implications of P=NP". It's not an explanation of the question at all.
don't post if you don't know the answer.
>>51726535
I doubt it, but it would be hilarious if it were the case. Theoretical computer scientists everywhere would realize that they're all morons.
>>51727243
There are literally 2 separate threads on reddit that turn up if you google "explain like I'm five p np". What didn't you understand from the two top-rated answers? I'm not going to go through all the work of explaining this to you if there are adequately descriptive answers out there.
>>51727762
but that's what would happen right? If P=NP then that means there exists an algorithm that can decrypt a 128-bit aes key as fast as the algorithm that checks whether the key you entered is correct or not.
Basically 128-bit aes decryption would take a specific time to decrypt instead of an unknown time (ie brute force attack).
>>51727740
Thing is, it depends on the solution that is found. If we're talking breaking AES in O(n^2), throw it in the trash, but it's also possible that we only find an O(n^20) algorithm or something like that, in which case there's no real risk.
>>51727845
>but that's what would happen right?
yes, but like I said, you've only given a very stupid overview of the implications of P=NP. If someone wanted to know what the question was about, your answer provided no insight to that.
I shouldn't have to poke you with a stick to get you to give a useful, relevant answer like this. If someone has a genuine, serious question, answering with a glib "encryption will be on suicide watch if it is hyuk hyuk" response is just a waste of space. And frankly it contributes to people getting annoyed with tripfags, because we associate these unhelpful posts with whatever salient details are present, like in this case a trip
>>51727845
Then you've only proven key decryption and checking to be in the same complexity class as key verification, I don't see how it guarantees it's going to be in the same order of complexity. High-order polynomials still suck.
> P = NP
It probably doesn't.
>>51726535
https://cusj-dev.journals.cdrs.columbia.edu/wp-content/uploads/sites/15/2015/04/Alston_2015_CUSJ.pdf
https://github.com/ad-alston/PolynomialSubsetSum
>>51727880
>yes, but like I said, you've only given a very stupid overview of the implications of P=NP. If someone wanted to know what the question was about, your answer provided no insight to that.
Oh ok. I'm sorry. It's just anon also asked "who gives a fuck?". I should have first started my post with, "You should give a fuck because.." and made it clearer how most encryption would become useless.
I'm not trying to become a cancerous tripfag. I'll try and make better posts next time.
>>51727944
Ah okay. Thanks for clarifying the part you were replying to (which I honestly didn't even notice in his post originally). I was overly harsh in that case. Sorry for that.
absolute shit of a thread
>>51727900
Because checking the solution to NP aka (encryption key) takes like 2 seconds. If P=NP then there exists a way to crack NP aka (encryption key) in the same time it takes to check the solution right?
I'm new to P=NP so please correct me if I'm wrong.
Absolutely not. non-deterministic polynomials are here to stay. These fuckers have been studied for hundreds of years and nobody can find a magical algorithm to solve them in a specific time frame.
>>51727394
>>51727644
Thanks, anon. Wish I could upboat you here.
Yes. There has to be easy solutions for NP type problems, we just haven't found them.
Can you prove easy NP solutions don't exist?
protip: you can't
>>51726535
P = 0 or N = 1.
>>51728233
>Yes. There has to be easy solutions for NP type problems, we just haven't found them.
just to play someone (not necessarily devil)'s advocate here, *why*?
Your argument is fundamentally unfounded. "We can't disprove it" is like the antithesis to purely logical thinking.
>>51726535
This is like asking if the flying spaghetti monster is the one true creator. We. Don't. Fucking. Know.
We can't prove P=NP but we also can't prove P≠NP
>>51728233
>Can you prove easy NP solutions don't exist?
Can you prove that the Devil doesn't exist?
>>51727243
Watch the video where OP's image is from.
>>51728245
niger
>>51726554
or p=0 you pleb
>>51728253
For now.
>>51728253
Given its implications on our lives (especially the lives of us who are pretty heavily invested in technology and, by proxy, in encryption), it's not unreasonable to opine on this and discuss the implications.
You're dismissing this entire discussion like we shouldn't even reckon with it unless we find that P=NP, but the entire exercise of discussing it might be the thing that leads us to a discovery that P=NP, or the logic that rules it out.
>>51728256
Because one can deduce a video source (presumably from youtube) from a still picture.
>>51728255
No...
>>51728284
https://www.youtube.com/watch?v=YX40hbAHx3s
>>51728284
>>51728353
You can literally get that from reverse image searching you fucking inbeciles.
>>51727394
>n^x for input size n
what i don't understand is what the size of "n" is measured in. are you talking about number of inputs? i don't understand what "input size" is actually represented as in this scenario.
>>51728280
I think it's a waste of time and just purely intellectual masterbation. People shouldn't worry about it like whether god exists or not.
Wasting time on problems that might never have a definitive solution is insanity to me.
Look, say we one day prove P=NP. horray. But one day we will stumble into a new NP problem that we will have to prove has an easy solution. Then more will crop up and you will have to keep disproving them over and over again for eternity.
We don't even know how many NP problems there are, there could be trillions of them.
>>51728353
thanks
ignore the rude anon that replied to you
>>51727243
Let's say that there is a really complicated equation. You can check if an answer is correct in a few steps (let's call them polynomial time), but can the computer arrive at the correct answer in about the same, polynomial, time?
That about sums it up. Current research about it points that it can only be known the answer with a quantum computer.
>>51728391
nice fallacy you got there
why do you assume people that are working on this problem are wasting their time? why does it matter to you that they do it? are you a part of it somehow?
>>51728353
Hey, thank
Would you mind doing my homework while you're at it? it's not hard I'm just lazy
>>51728391
>We don't even know how many NP problems
Actually, there is an infinite amount of them (cardinality 4 if I remember correctly).
>>51728391
I'm sure that high level reasoning seems like intellectual masturbation to people who struggle with it, but the implications are meaningful and it's worth preparing for either outcome, to say nothing of actively trying to answer the question.
And we might find ways to reduce NP problems to P by entire classes of problems, rather than individual ones, which means we're not solving potentially trillions of problems one by one the way you're suggesting.
Moreover, we're operating more or less on whether P probably = NP. By that I mean, if our faith is in NP problems being reducible then we need to start preparing for when an NP problem like AES encryption gets reduced to a polynomial time problem.
>>51728427
Post it.
>>51728411
You can check if an answer is correct in a few steps (let's call them polynomial time), but can the computer arrive at the correct answer in about the same, polynomial, time?
Wrong. If P=NP then that means there exists a way to solve the NP problem as fast as checking it.
>>51728473
That's literally what I said though.
>>51728446
Thank you bb
>>51728379
depends on the problem. Number of elements in a list is one measure.
>>51728379
Some anon correct me if I'm wrong, but I believe that n is the number of simple computations, i.e. any of the 4 basic operations (+, -, *, /).
If a program does only a multiplication, the result is computed in n time (the time it takes for the computer to compute the multiplication). If a program does various multiplications, say a for loop that multiplies a number by the loop's counter and it loops 5 times, the problem becomes n^5.
>>51728483
You said "about" which implies a longer or shorter time.
>>51728418
>why do you assume people that are working on this problem are wasting their time?
Because they have to prove all NP problems are P problems or vice versa and like >>51728435 said, there might be an infinite amount.
>why does it matter to you that they do it? are you a part of it somehow?
It doesn't but I still think it's a waste of time.
>>51728508
>>51728507
thanks family
>>51728512
>which implies a longer or shorter time
Yeah. I mean, it can either be, or not be, right?
Is OP trying to answer the million dollar question
>>51727139
>inb4 you're a NEET
>>51728550
>Because they have to prove all NP problems are P problems or vice versa
We don't know if all numbers divisble by 2 are even because we haven't checked them all since there are infinite numbers.
>>51728553
technically we don't know because we haven't found the fastest possible solutions to the few magical (ie actually P problems) NP problems that we might have already solved.
This shit gets really weird as you start to realize that there exists an infinitely small chance that solving NP problems might be faster than checking them.
>>51728512
>a longer or shorter time
Are you really this dumb? That's like saying that an answer can either be correct or wrong.
>>51728581
Thus my point that proving whether P equals NP or not is in the grand scheme of all things pointless and a waste of time.
Look at the nigers throughout history trying to prove god exists or not. All of them spent time on a problem that virtually has no solution since there an an infinite amount of factors you have to account for and prove/disprove.
This is why I'm an atheistic agnostic.
In that same sense people should just tell themselves what's most likely but deep inside their skulls accept they could be wrong.
Anyway P=NP is unsolvable, let that sink in for a minute.
>2015
Unironically believing in NP fairytales. C'mon g, I thought you were better than this.
>>51728568
yes
what if P=NP is of a hardness we havent even discovered yet.. like an exponential exponent...
Not relevant
>>51728671
Then solve them you fucking niger!
>>51728671
>fairytales
Oh look, another basement-dwelling neckbeard who thinks that he's brighter than some of the best minds to have ever lived.
>>51728647
>This is why I'm an atheistic agnostic.
This triggered me.
I'm a fluidsexual omnidimentional god trapped inside a man's body.
Your trolling gave me PTSD and AIDS.
>>51728671
/g/ is shit anon
>>51728694
stupid frogposter
>>51728581
Yes we do know that because it's simply an easy thing to extrapolate. Every whole number divisible by 2 will be even. Hell, the definition of "even number" is to be divisible by 2. It can either be 4 or 5405518648815681868, if the rightmost digit is even, the whole number will be even.
>>51728682
Well, P=NP is an NP problem in itself, that's the main problem of the whole thing. That's due to the fact that we don't know exactly how many NP problems there are, or if they're even finite, so we can't prove that all of them can be P.
>>51728694
I don't have to. Humans will. We have always found solutions to mathematical problems. What makes you think finding solutions will stop now?
>>51728695
Look, NP problems are just P problems that we haven't found easy solutions to. Bet you next year 1 or two more NP problems will be revealed to be P nigers pretending to be NP problems. This cycle will go on infinitely until we one day prove there are a finite amount of NP problems and we solve all of them.
>>51728581
Let n be an integer. n is even if there is some integer k such that n = 2k
There is your proof
>>51728742
>>51728774
My point is that to prove something you don't have to prove every single case.
P=NP might be much harder than the example I provided, but saying to prove that P=NP or P!=NP you have to check every single case is stupid.
>>51728508
No. Operators are done in constant time. n most typically describes the number of items to be iterated or recursed through. i.e. iterating through an array takes O(n) time where n is the length of the array.
Big O notation describes how a function grows as it becomes arbitrarily large, in which case the fastest growing piece of the function is the only part that matters because any slower growing piece of the function becomes immaterial.
>>51726535
Unsolvable. Abandon hope while you still can.
>>51728868
thistbhfam
>>51728788
It's not that stupid really. Since each and ever problem in NP has a level of complexity, and varying levels of it, it's hard to extrapolate from only proving that one NP problem is P.
>>51728866
You're right, thanks man. It's been a while since I've had my algorithms classes.
>>51728866
So if we have something in the form offor(int i=0; ...) {
for(int j=0, ...) {
matrix[i][j];
}
}
Does the problem become O(n^2)?
Apologies if the formatting is poor, I'm on mobile.
>>51728868
Let's not kid ourselves, this is really the best we can do.
>>51728916
You seem to think the only way to prove either that P=NP or P!=NP is to check all problems.
Do you think that Fermat mentally calculated every inifinte possible a, b, c, and n for a^n+b^n=c^n to be able to say that no whole numbers a, b, and c, and no whole number greater than 2 for n would satisfy this equation?
>>51726535
Sudoku is NP now?
>>51729035
For humans, yes.
>>51726535
unlikely, my experience is that the world sucks and there's no free lunch. Like, can't we extrapolate from no free lunch (for optimizations problems) and conclude p != np ... I know this isn't sound in any way but just a thought.
>>51728768
>assuming humans live forever
>>51728435
>cardinality 4
That's just 4, anon. You probably mean \beth_4 = P(P(P(P(ω)))). But then again, that's also wrong, since the class of all decision problems has cardinality P(ω).
>>51729031
Again, every problem in NP will have different complexity. From this fact alone it is nearly impossible to make such a mathematical extrapolation. If you wanted to use an analogy, you'd need to have something similar to the Fermat equation but with all real numbers.
>>51729127
>every problem in NP will have different complexity.
Not claiming otherwise. It doesn't disprove what I'm saying either.
>From this fact alone it is nearly impossible to make such a mathematical extrapolation.
Nearly impossible is another word for very hard, and very distict from impossible.
I'm sure you realize that if it were an easy problem it would have already been solved. The last of Fermat's theorems to be proven wasn't an easy one either, but no one sat and tallied every single number to prove it.
>If you wanted to use an analogy
You're missing the point of analogies as much as you're missing the point of MY analogy.
Analogies are to explain something in a more familiar domain. If I were to make an analogy in the same domain you had issues understanding, my analogy would be worthless.
>>51727644
>If not, then there exist problems which can not be solved in polynomial time on a classical computer.
There already are such problems. This is only about the relationship between P and NP, but there are NP-hard problems not in NP and there are undecidable problems that we can never solve.
>>51729222
I get that, but your analogy was analogous to using the working of the human digestive system to explain quantum mechanics. It was something in a completely different realm. Most of mathematics works on deductive reasoning, if one case can be proven, then all following cases are true aswell. In the case of P=NP, you can't say that solving a chess game is as simple as the folding of a protein. We're talking about many varying degrees of complexity.
>>51729321
Stop your pseudoscientific bullshitting, plox. Go pick up a book instead of masturbating over analogies.
>We're talking about many varying degrees of complexity.
And we've formulated sufficient conditions for when a single NP problem being in P implies NP ⊆ P.
>>51729321
>I get that, but your analogy was analogous to using the working of the human digestive system to explain quantum mechanics.
That can be a perfectly valid analogy if it drove the point across.
>It was something in a completely different realm.
Again, not only do analogies not have to be in the same realm, but the fact that they're not is kind of the point. To help you understand a realm you're not familiar with by drawing similarities from one that you are.
My analogy consisted in the same way that you don't have to check every number divisible by 2 to see that it's even, you don't have to check if every case of NP = P to know that they all are or aren't.
>>51728989
Essentially, yes. However, if you were thinking about how long it would take to solve something using iteration over a matrix you would want to think about each dimension individually if the matrix isn't square.
Big O notation only tells you how it will grow when it's infinitely long, it's not always the best way to describe how long something will take to run.
>>51729432
You're assuming that you can use the same deductive reasoning you use with mathematics in real world problems though.
>>51729491
Meant to say inductive, not deductive.
>>51729491
Are you implying that the problem of wether P=NP isn't a mathematical one?
https://www.youtube.com/watch?v=Yse3etpnqFA&feature=youtu.be&list=PLrNmXMVD0XDS6RFmIpGlmzjtshKyvNtC-
This is a lecture from COS126 at Princeton, and I think it does a good job of explaining P ?= NP and the solvability of problems in general
>>51729640
meant for
>>51727243
>>51729491
>you can't use mathematical proofs for mathematical problems because the results might be applicable to the real world
Nigga wat.
>>51729031
Fermat didn't know shit. He thought he had a proof, mother fucker didn't have a proof. He was full of shit on that problem. Otherwise solid dude.
>>51729491
homie... this is a mathematical problem not a real world one. Get it together man.
OP, what did you think of that quiz we took last Thursday?
>>51728167
Not necessarily. It depends on the algorithm found, so it could still take you a lot of time to generate the key. So it's not like we'll have people coming up with keys on the spot, like in the same amount of time it takes to verify a key. The major drawback everyone worries about is that someone trying to crack a code can actually be guaranteed to generate the correct key with enough time. So someone that leaves a computer running for 6 months with a O (n^200) algorithm might crack your shit. It'd be pretty autistic, but when it comes to credit card information and whatnot, people will do it. They already do it with brute force algorithms that realistically will never get the job done in their lifetime.
It seems extremely unlikely, but I would absolutely shit myself in awe and excitement if P=NP.
>>51729055
Not how that works.
>>51726878
Who the fuck wouldn't be happy if P = NP? The question is whether you think P = NP.
>>51726878
>I doubt anyone here has a firm grasp of it
>tipping_fat_fedora_neckbeard.tga
>>51731170
>Who the fuck wouldn't be happy if P = NP?
people who rely on solutions to be more costly than verification. Basically, everyone currently invested in encryption.
So, basically everyone.
>>51727845
>then that means there exists an algorithm that can decrypt a 128-bit aes key as fast as the algorithm that checks whether the key you entered is correct or not.
Of course not. It means that both are gonna be polynomial time. But complexity (big O notation) is an equivalence class, just like modulo. Having the same complexity means the algorithms take *similar time*, up to a fixed multiplicative factor c, it doesn't mean the algorithms take the exact same time.
It could mean, if algorithm a takes 5 seconds, algorithm b takes 500 or 50000 seconds. But most importantly, complexity is about scaling. If the input size makes the algorithm a jump from 5 seconds to 15, it'll make algorithm b jump from 500 to 1500, and not 150000000.
>Basically 128-bit aes decryption would take a specific time to decrypt
It already takes a specific time to decrypt, if you mean finite.
And it'll never take a totally specified time, if you mean absolute accuracy.
Holy shit, algorithms are all about upper and lower bounds, scaling, and statistical methods approximating their times and behaviour most of the time.
They're not simple arithmetic.
Why the fuck are the most ignorant voices the loudest?
>>51731266
Could algorithms just shift to something that isn't NP such EXPTIME?
>>51726535
>Does /g/ think P = NP?
I think there are intricate structures/classes between P and NP.
Dividing problems between P and NP is like [overused quote] diving the universe between bananas and non-bananas [/overused quote].
>>51731347
>Why the fuck are the most ignorant voices the loudest?
She's the village idiot, don't feed her after 21:00 and don't cum on her.
>>51728574
No, I'm just an honours graduate from a renowned german university.
>>51731170
>Who the fuck wouldn't be happy if P = NP?
Pretty much every Cryptographer and people in ITSEC
>>51727278
the fact that you know that is reddit
>>51731233
>>I doubt anyone here has a firm grasp of it
>>tipping_fat_fedora_neckbeard.tga
You really showed me with your fresh opinions here
>>51727644
Doesn't the existence of NP-complete problems kind of prove that P is not equal to NP? I mean practically speaking it's not like someone is going to magically come up with an algorithm that solves an NP-complete problem in polynomial time, right?
>>51733380
No it doesn't. X being NP-complete simply means that the existence of a deterministic polynomial time algorithm that decides X would imply that there exist a deterministic polynomial time algorithm for every problem Y in NP.
>>51733380
>Doesn't the existence of earth-inhabiting animals kind of prove that there are also aliens?
>>51733319
What degree?
>>51733711
Computer Science with a minor in Mathematics
>>51726535
Given that only one problem not being solveable "quickly" means that they are not equal i'm going say that they aren't equal
>>51728868
This is actually my bet. I don't think P=NP, but I think it's probably impossible to prove P≠NP.
Let's face it, anyone proving either would collect a lot of bets.
>>51734265
So you're flipping burgers too?
>>51726535
Hopefully not.
>>51727740
This isn't necessarily true. Sure, any useful encryption is in NP, but, so far, nobody has proven that it is NP complete. The only problems affected by the P=NP question are NP-complete ones, so most encryption may still be fine, for all we know.
OP = FAGGOT
>>51728499
8a) 1,1,0,0
8b) 0,0,1,1
8c) 1,1,0,0
8d) 1/n,1/n,0
8e) 0,1/n,1/n
8f) No (not if the initial state phi of 2nd reg is unknown)
>>51731436
second this question
>>51731528
*he
>>51727944
>I'm not trying to become a cancerous tripfag
that's pretty easy, just don't trip
>>51736200
>encouraging cancer to not tripfag
You're not helping us anon.
>>51736200
thanks for bringing that conversation back up and stirring the pot several hours after the fact. definitely not cancerous behavior
