/sci/ - Science & Math

p is a polynomial time solution. imagine a loop that finds my toothgbrush in my luggage...that's a problem in P because it takes only 1 run through the list to find my toothbrush

but say i want to get the best combination of items to put in my suitcase such that it's only 50 lbs. that requires testing all combinations of items to find the one that is closest to 50 lbs.

if you had a "non-deterministic" machine, that means you could check every combination of items at once, and then you could find the best combination in "non-deterministic polynomial time" (NP) but in real life this means that there are an "exponential" number of things that you have to check all the possibilities yourself.

NP problems are a subset of exponential class of problems, but it is unknown whether they can be reduced to regular polynomial time.

>>5964142

so lets say someone found the solution to this problem, what practical use would it bring to our world ?

Your pee pee(P) is said to be naughty(NP) iff it gets hard.
Open problem: Is all pee pee naughty?

I don't know

>>5964203

Thank you anon. Now I know how to break the ice with this girl in my math class.

>>5964164
I think the problem is too philosophical. The concept of "problem", "decision problem" and things like that are too general too abstract, i don't think anyone can give an answer to that, the best we can do is to explore some other classes which are more subtle.

>>5964081
L: Problems of size n that you can solve in C*log(n) space
NL=coNL: Problems of size n that you can solve in C*log(n) space with a succession of random guesses that happen to be right
P: Problems of size n that you can solve in C*n^k time for some constants C and k
NP: Problems of size n such that IF IT HAS a solution you can find it in C*n^k time for some constants C and k with a series of guesses that happen to be right
co-NP: Problems of size n such that IF IT HAS NO solution you can find that in C*n^k time for some constants C and k with a series of guesses that happen to be right
PSPACE=NPSPACE: Problems solvable in C*n^k space for some constants C and k
EXPTIME: Problems solvable in 2^[C*n^k] time

Clearly
L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆EXPSPACE
NL⊊PSPACE⊊EXPSPACE
P⊊EXPTIME

>>5964081
Roughly speaking, P represents the set of questions to which a computer program can find the answer in a reasonable amount of time; NP represents the set of questions to which a computer program can find the answer in a reasonable amount of time with a hint.

Clearly, P is a subset of NP; if you can find the answer to a question without a hint, you can also find it WITH a hint. The question of P=NP is whether the inverse also holds -- whether every question that can be efficiently solved with a hint can also be solved efficiently without it. If so, a great many problems that currently can not be efficiently solved are suddenly solvable.

There are strong indications that P is not in fact equal to NP, meaning that there are problems for which the hint is essential to efficiently find a solution. There is no PROOF though, one way or the other, so it remains an open question.

>>5964164
>so lets say someone found the solution to this problem, what practical use would it bring to our world ?

None. Even a n^4 SAT solver would still be too big for most problems

>>5964224
Are there also indications that P is equal to NP? (ofcorse not as strong as that P is not eual to NP)

>>5964282
None that I can think of.