Can someone explain P=NP to me?

P=NP for all P if N = 1

t. mathematician

>>57028331
Or for all N if P=0

>>57028331
P=NP for all N if P = 0

It's about time complexity, how long an algorithm takes to run in general given sufficiently large inputs.
There's like O(logn), O(n), O(n^2), O(2^n).
So, if an algorithm runs in O(n) time, in general the size of the input scales linearly with the time it takes to run. O(n^2) P olynomial time, time taken scales polynomially based on input size, NP = Nondeterministically Polynomial time. Basically a nondeterministic turing machine can perform the algorithm in polynomial time.
But ignore that shit, it's basically the set of problems that take exponential time to compute, you can see that these aren't feasible solutions really, as the time taken grows exponentially with larger input sizes, and takes fucking forever.
Nobody has proven theoretically whether these class of NP problems, have or don't have solutions that run in polynomial time.

>>57028412
Are there O(n^n) algorithms that can't be done faster?

>>57028275
>Penis = No Penis
It's one of the many things degenerates here say

>>57028275
P=NP is utopist and utter non-sense
>muh let's make a god algo which can answer everything

there are some interesting results that suggest the p=np question can't be solved by conventional means. i'd look into it further, but the fact that so many smarter people have tried and failed to solve the problem is discouraging

File: really good mood.jpg (41KB, 500x667px) Image search: [Google]

41KB, 500x667px

>>57028500
This desu

>>57028443
Reminder that these actually sets we're talking about, I'm guessing you know some basic set theory.
So we say a problem belongs to the set of P, if there exists a solution to it that runs in polynomial time.
For all the other sets there exist formal proofs showing their relationships with other sets, like DTIME (problems with solutions that run in O(n) time) is a subset of P, but we just don't know the relationship between P and NP.

Although I'm rusty on this shit, I was too busy drinking myself to death during that year,

>>57028500

under most reasonable conditions, this is probably true

>>57028649
You can't prove all the time that a polynomial algorithm exists.
The easiest example is travelling salesman problem.
The current best solution to this class of problems is to develop more powerful machines which can compute
exponantial algorithms in polynomial time.
We're approaching the limit of the standard computing theories set by Church and Turing.

Take a look at Grover's algorithm, the gain with that kind of algorithms is insane, for now we can't find similar algorithms with "standard" computing.