[Discussion] P vs. NP

[RikTelner]

http://en.wikipedia.org/wiki/P_versus_NP_problem
http://simple.wikipedia.org/wiki/P_versus_NP

I stumbled upon this topic. P vs. NP. So far as I could understand from "simple" version of Wikipedia (the "en" version cracked me). They seek for method to find match amongst many results instantly without Brute Forcing it. Is that true?

So far I can thinks of this with my limited brain resources. There can't be no answer. Since if this could be possible, we would be able to divide by zero. Pin point exact location of aliens or prove existence of God.

What is your opinion about it?

[RikTelner]

There can be no answer*. Just realized about this foolish mistake I made.

[Hiroshe]

The set P contains all of the problems that are
1. decision problems (the answer is "yes" or "no")
2. can be solved in O(n^k) time for some contant k on a deterministic turning machine. (a deterministic turning machine is a computer which will do one action for the same state and tape, so pretty much a normal computer).

The set of PN contains all of the problems that are
1. decision problems.
2. can be verified in O(n^k) time for some contant k on a deterministic turning machine given a proof.

The P vs. NP problem asks if the set P is equivalent to the set NP. ie, if a problem can be verified in polynomial time (O(n^k)), can it be solved in polynomial time?

They seek for method to find match amongst many results instantly without Brute Forcing it. Is that true?

Polynomial time is a lot slower then "instant" constant time O(1), so not quite. We are trying to see "if we can prove that a proof for the answer can be verified in polynomial time, then can we prove that the answer is findable in polynomial time?"