I heard that NP problem is a problem which can be solved in polynomial

>>7959724
For many NP problems, deciding a solution is the process that's NP. Checking a solution is usually P. An example is the knapsack problem, that is, optimizing for maximun value the load in a container given weight and value of all items and a max weight. Its very easy to check if something is a solution is valid (sum weights. Is it over the max?), but not so much to find that solution.

>>7959724

Find the roots to some polynomial like [math]3x^13 - \dfrac{1}{5}x^7 - 2x^2 + x^2 = 0[/math]; the actual problem will take a relatively long time to compute compared to checking the solution (i.e. plug in the presumed solution, is the number 0 or not? quick and easy).

>>7959874

Whoops, meant [math]x^{13}[/math]. Anyway that's just a example of something ridiculous that will take a long time to solve.

>>7959875
x=0

did not take long at all ayy lmao

>>7959874
http://www.wolframalpha.com/input/?i=solve+%283*x^11-%281%2F5%29*x^5-1%29*x^2+%3D+0

:^)

P=NP

It's just the algorithm to prove that takes exponential time to discover.

>>7959724
A good example of this is factoring very large numbers with few prime factors.

Very easy to check if a number is a factor (just divide) but extremely difficult to find those factors in the first place. RSA encryption is based on the difficulty of this problem.

https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29

>>7959724
I think it's because we're only considering the non-deterministic TM's best case. There's some sequence of random decisions that let you solve the problem quickly if you are lucky and guess them correctly. This information can be thought of as a quickly verifiable proof that the answer is what it is.

for once, the thread question was concise and clear. he asked WHY IS IT EQUIVALENT?

stop spamming examples and weird suppositions

You can pass the non deterministic choices to your machine as certificate to make a deterministic machine that verify your solution

>>7959778
'The class of questions for which an answer can be verified in polynomial time is called NP, which stands for "nondeterministic polynomial time."'

I'm talking about that statement, which is different from what you're saying

It's actually somewhat intuitive.

Imagine the branching solution tree of the NDTM.

Going through the entire tree is hard. Verifying a solution though is as simple as just walking down one branch of the tree.

>>7960728
that makes sense. NDTM checks all bifurcations at then same time, so it is like it was checking a single branch (i.e., the answer)

>>7959883
I know you are joking, but for polynomials of degree n, solving the polynomial has a time complexity higher than a polynomial of degree n