p = np
Images are sometimes not shown due to bandwidth/network limitations. Refreshing the page usually helps.
You are currently reading a thread in /g/ - Technology
You are currently reading a thread in /g/ - Technology
![pvsnp[1].jpg](https://i.imgur.com/tXMVwWn.jpg "pvsnp[1].jpg")
Am I understanding this correctly /g/?
In simple terms does P=NP mean
>1 + 2 = x
may or may not be faster than
>3 = 1 + 2
>>53686923
Nope, you're not understanding this correctly.
What you've apparently learned is the oversimplified layman metaphor, it's nice to have a rough idea of what we're talking about, but if you try to draw any conclusion from that "knowledge", it'll probably be wrong.
>>53686923
No, you're not at all understanding this correctly.
P vs NP is a problem which roughly asks if a problem is quickly verifiable by a computer, then is it also quickly solvable by a computer? If P=NP, then problems verifiable in polynomial time are solvable in polynomial time. If P =/= NP, then there are problems (NP problems) that are harder to computer then to verify their solution.
A lot of people still present P=NP as if everyone is holding their breath waiting for a proof, but it's not that big of a deal. A majority of people will be happy to assume P!=NP or perhaps that it's undecidable.
But the P=NP camp has few supporters these days.
P=NP
P/P=NP/P
1=N
Solved
>>53687953
>>53687953
DELETE THIS NOW
>>53686923
P=NP | P=0 || N=1
Guys idiot here, do I understand correctly when I imagine p=np as a sort of the multiple ways of reaching one result? Like
100=10*10
100=1000/10
100=1*100
Isnt that what the whole p=np problem is more lr less about?
p: R\{0}
Solve for n:
p = np |:p
n = 0
Solve for p:
p = 0•p
p = 0
p cannot by definition be 0 => p≠np.
Q.E.D
>>53687035
To further expand on this since this is probably confusing to most other people...
This is like factoring in algebra. You remember that shit? Let's turn [ax^2 + bx + c] into [(x + d)(x + e)]. Yeah you do. You probably hated it.
If you believe P=NP then you believe there is a way to solve all factorings by a simple trick, quickly and easily, without fail.
If you believe P!=NP then you believe it's always going to be a shit show and it'll always be that pain in the ass.
The reason this is important is for several reasons in computing. Let's take cryptology for one. If P=NP then cryptology is ultimately useless. There is a trick to quickly and easily break encryption. If P!=NP is real then, well, cryptology is still useful because the time it takes to crack most encryptions the info is now no longer relevant.
So, there you go. Enjoy.
>>53691704
>>53691704
Quadratic factoring is an interesting case, because the naive approach that most people starts with is difficult and cumbersome. So it feels like a hard (ie: NP) problem, until you learn the quadratic forumula which gives you a simple (ie: polynomial time) solution.
There also exist general formulas for factoring cubic and quartic equations, but the fun stops there. There are no known algorithms that can factor polynomials of degree 5 and higher in polynomial time. Although we can prove that the roots exist, we just have never found an algorithm that does it quickly.
Saying that P=NP means that those faster algorithms exist, but we just aren't smart enough to find them. Saying that P!=NP means that those algorithms don't exist, but proving it would also be an NP problem.
>>53687066
This.
P != NP is the consensus among anybody I've asked who's sufficiently informed about the subject.
It's just finding a proof that's difficult.
It's like Fermat's Last Theorem or the Goldbach conjecture. All tests, signs and other theorems we've cross-linked to it support the conjecture - but actually proving the fact is difficult as hell.
In general, disproving something that's false is _significantly_ easier than proving something that's right. (Because if a counter-example exists, it's generally easy to find - but if none exist, it's hard to prove that fact). N!=NP is pretty much an archetypal example of this phenomenon.
http://www.scottaaronson.com/blog/?p=1720
>>53691704
P=NP would entail many seemingly bizarre statements, such as:
>Encryption can't work
>Hash functions don't exist
>Everybody who can appreciate a work of art can also create that work of art
>We can build a machine that will come up with a valid proof (or lack thereof) for any theorem you give it
etc.
i don't know, i failed math
p = np
> p/p = np / p
> 1 = n
why is n = 1? I thought it was a variable, not a constant
>>53693114
That's not what p = np is about.
>>53693114
‘NP’ is a single name. It's not ‘N·P’.
>>53691704
>If P=NP then cryptology is ultimately useless. There is a trick to quickly and easily break encryption.
No, common misconception.
A polynomial time algorithm with massive constant factors (say n^100) is just as practically infeasible as an exponential time one.
>this thread
of course P =/= NP
P = P
>>53686923
Let's say you have a really large number which is the product of two unknown prime numbers. If I were to tell you "find the two prime number factors", this would in general be a challenging task. It would take you a long time to do it, even if you used the best factoring algorithms that we have. However, if I gave you the two factors, you would quickly be able to verify that they are in fact factors of the number. You just multiply them together and see if it's equal to the large number, which is comparatively easy, even for large numbers.
If P!=NP, it means that this type of cases is inherent to the mathematical system. That is, no factoring algorithms may ever be as fast as simply multiplying the two numbers together and checking if it's the same number. This is what most computer scientists and mathematicians believe, since we do not have any fast factoring algorithms (for example) despite considerable effort.
If P=NP, it means that this type of cases is simply because of our lack of knowledge. It means that there are fast factoring algorithms, that are as fast as multiplication, we just haven't found them yet. Computer scientists and mathematicians generally do not believe this, and it would have considerable consequences. A constructive proof that P=NP would ruin at least public key encryption as we know it, but it seems highly implausible that such a proof will ever be found.
>>53686923
hey fucktard, NP is it's own value. This is not algebra.
NP is short for Non-Polynomial Time.
P is for Problem.
the problem is not solvable in polynomial time, meaning it's impossible to solve with the current state of mathematics. meaning the only one who can solve the problem is someone who's smart enough to discover more mathematics. fuck.
>>53694053
>NP is short for Non-Polynomial Time.
Nondeterministic Polynomial Time*
>>53686923
let the pretty picture assist you
>>53693483
This is the apex of intelligence.
>>53694053
>NP is short for Non-Polynomial Time.
NOOOOOOOOOOOO
>>53694121
damn son, you would have looked smart if you were only 4 minutes faster, or kept your mouth shut after scrolling one more post
>>53687035
slight correction: it's not about polynomial time but deterministic polynomial time
>>53687953
Wrong, you fuck!
P=NP
NP - P = 0
P(N - 1) = 0
1st solution: (P, N) = (0, R)
2nd solution: (P, N) = (R, 1)
>>53693332
>two variables
>are single variable
the fuck are you on about?
https://youtu.be/YX40hbAHx3s if you fail to understand all of this
>>53694216
Variables? Aren't P and NP sets?
>>53693591
>A constructive proof that P=NP would ruin at least public key encryption as we know it, but it seems highly implausible that such a proof will ever be found.
Proving P=NP would not ruin anything since a P time integer factoring algorithm still wouldn't magically fall from the sky (unless the proof was from such an algorithm in the first place).
And even if you did find a P time algorithm it's still no guarantee you'll be able to break any encryption in your life time.
P=NP is really a red herring in terms of 'breaking encryption', what matters in keeping ciphers secure is making it practically impossible to break, and that can happen with or without polynomial time algorithms (and conversly, just because you find a polynomial time algorithm doesn't mean you'll have enough real worls time to break anything).
Encryption is broken when someone presents an actual program, running on actual computers breaking actual ciphers - theoretical results doesn't really matter.
>>53694237
P and NP are both sets, yes.
I don't know what the fuck >>53694216 is talking about.
>>53691929
>>Everybody who can appreciate a work of art can also create that work of art
This seems far fetched
>>53694553
Slightly far-fetched, and admittedly I misrepresented the argument.
The argument goes: If it was possible for physical machines to simulate nondeterministic turing machines efficiently (which is basically what P=NP would require), then we could reasonable expect that our brains - or at least some thing around us - would be capable of doing so as well.
If we lived in such a world, we would all have brains capable of efficiently finding solutions to arbitrary problems given the only ability to discern what is and isn't a solution.
And to use an analogy, it means we would be able to write a mathematical proof or beautiful work of art simply by leveraging our ability to understand or appreciate one.
The fact that we do not live in such a world is an argument against believing that such physical machines are possible (or at least feasible).
>>53694657
But our brains aren't Turing machines. This seems pretty silly.
>>53695678
The turing machine is just an abstract way to formulate the computational power.
As per the church-turing hypothesis, it doesn't matter whether you're considering turing machines, SK combinators, cellular automata or (presumably) the human brain - they're all equivalent in terms of their complexity classes.
We have no evidence that the human brain can do anything a turing machine can't (and vice versa).
>>53686923
Horribly wrong
The idea of p=np is this:
If a problem is very easy to prove right with a given answer, does it mean it is easy to solve in the first place
Take this, if you were to find a box of parts, each part has 8 distinct features it may or may not have, and each one may be oriented in a different direction
Each part must be connected to one of the other parts based on how they are configured/oriented.
If they came together it would be really easy to check if each set met the criteria, but trying to determine how to best configure them would be almost impossible to solve
>>53695969
Assume there are a few hundred parts in the box, and that problem would take years on even a super computer because you literally would need to compute every possible combination
how can i see the non closure under complement with the machine-based definition?
>NP is the set of decision problems solvable by a non-deterministic Turing machine that runs in polynomial time
who here actually tried to solve this?[hide]for more than 3 years[/hide]
