>>7690809

P = NP postulates that there are no non linear functions that require an exponential amount of iterations given the input that can't be reduced to non linear functions that only require a polynomial number of iterations for the same task.

It's a meme.

Let n = 1
P(1) = P
NP=P
P=NP

>implying modern science isn't stuck too far up it's own ass for intuition

There are a class of problems - P - which take a short amount of time to solve and the answer can be verified in a short amount of time.

There is another class of problems - NP - which take a huge amount of time to solve, but the answers produced can be verified very quickly (as quickly as with a P problem).

P vs. NP is based on the point that we currently have nothing to prove that all of these NP problems aren't just P problems that we are too stupid to think of a good solution to. The goal of P vs. NP is to provide a mathematical proof that either P = NP or P =/ NP.

>>7690809

Is being drunk just as good as being sober

A problem is P if it can be solved by a deterministic algorithm with polynomail growth.
A problem is NP if it can be solved by a non-deterministic algorithm with polynomial growth.

Polynomial growth is rather general, but essentially it means it grows at most at a rate of x^n for some finite n. Which can be quite large growth, but compared to exponential growth and even larger growths, it's nothing. It might take 4 minutes with 2 variables, 9 minutes with 3 variables, 16 minutes with 4 variables. This is polynomial growth. Exponential growth would be 4, 16, 64, 256. It quickly becomes impossible to keep up with.

So what is deterministic vs nondeterministic algorithms? Essentially it works like this: a deterministic hiker comes to a crossroad. He has to choose between path A and path B, not knowing which path leads to the where he wants to go. In order to find where he wants to go he has to traverse each path, one at a time, going backwards when he reaches a dead end or somewhere he's been before. His travel time is the sum of all the distance he's walked. A nondeterministic hiker is able to take both paths at the same time. As long as some selection of paths ultimately ends at where he wants to go, then he gets there. The distance he has walked is simply the distance from where he started to where he wanted to go. All the paths that didn't lead the right place or got there slower are kind of just ignored (don't quote me on this specific).

Now, obviously the deterministic hiker did a lot more work. But the question that is as-of-yet unanswered is whether the amount of work he did ever has a fundamentally a larger growth rate than the nondeterminuistic hiker. To me it seems like it would intuitively be so for the same reason NxN (Q) is the same magnitude as N. But obviously it's not that simple.

>>7690939
er sorry, let me fix those last two sentences:
>To me it seems like it would intuitively seem like they have the same fundamental growth for the same reason NxN (Q) is the same magnitude as N. But obviously it's not that simple.

>>7690939
The problem with the N <=> NxN idea is that as soon as you have a scenario where the path splits more often, you have a 2^N analogy.

>>7690883
This is the best explanation in the thread, and also the one I was given during my undergrad.