Revolusi Sains Indonesia

Mari masyarakat Indonesia gempur masalah ini beramai2x!!!!

http://en.wikipedia.org/wiki/Computational_complexity_theory

The P versus NP problem and other open questions
[edit] P = NP
Main article: P versus NP problem
See also: Oracle machine

The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. The complexity class NP is the set of decision problems that can be solved by a non-deterministic Turing machine in polynomial time. This class contains many problems that people would like to solve efficiently, including the Boolean satisfiability problem, the Hamiltonian path problem and the vertex cover problem. All the problems in this class have the property that their solutions can be checked efficiently.[3]

Since deterministic Turing machines are special nondeterministic Turing machines, it is easily observed that each problem in P is also member of the class NP. The question of whether P = NP (can problems that can be solved in non-deterministic polynomial time also always be solved in deterministic polynomial time?) is one of the most important open questions in theoretical computer science because of the wide implications of a solution.[3] If the answer is yes, many important problems can be shown to have more efficient solutions that are now used with reluctance because of unknown edge cases. These include various types of integer programming in operations research, many problems in logistics, protein structure prediction in biology, and the ability to find formal proofs of pure mathematics theorems.[4][5]

The P = NP problem is one of the Millennium Prize Problems proposed by the Clay Mathematics Institute the solution of which is a US$1,000,000 prize for the first person to provide a solution.[6]

Questions like this motivate the concepts of hard and complete, explained below.

Berikut abstract pendekatan quantum computation untuk memecahkan permasalah ini: