Nondeterministic polynomial time

NP-Complete problem Decision problem (one for which the solution is yes or no ) that has the following property The decision problem can be solved in polynomial deterministic time if all decision problems that can be solved in nondeterministic polynomial time are also solvable in deterministic polynomial time. 

GA = genetic algorithm LUP = locally updated planes NP-complete = nondeterministic polynomial time complete. 

Let P be the set of all decision problems that can be solved in deterministic polynomial time. Let NP be the set of decision problems solvable in polynomial time by nondeterministic algorithms. Clearly, P cNP. It is not known whether P = NP or P NP. The P = NP problem is important because it is related to the complexity of many interesting problems. There exist many problems that cannot be solved in polynomial time unless P = NP. Since, intuitively, one expects that P c NP, these problems are in all probability not solvable in polynomial time. The first problem that was shown to be related to the P = NP problem, in this way, was the problem of determining whether a propositional formula is sat-isfiable. This problem is referred to as the satisfiability problem. 

It is unlikely that any NP-complete or NP-hard problem is polynomially solvable because of the relationship between these classes and the class of decision problems that can be solved in polynomial nondeterministic time. 

---