Np-Complete
The term NP-Complete refers to a complexity class of decision problems. A "complexity class" is simply a collection of computational problems that all have the same bounds on time and space, and a "decision problem" is a problem for which the answer is "yes" or "no." This is equivalent to a computational function that has a range comprising just two discrete values, such as 0 and 1.
NP-Complete is a subset of NP or "Non-deterministic Polynomial time," which is a set of problems for which answers can be checked by an algorithm whose run time is polynomial in the size of the input. The complexity of algorithms is generally measured using "Big-O" notation, which is a theoretical measure of how quickly an algorithm will run in terms of the time or computer memory required given the size of the problem itself. The number of items in the problem typically defines the size of the problem.
An algorithm that runs in "polynomial time" has an average running time that is no more than a polynomial function of the size of the input. Polynomial algorithms have running times formally expressed as:
where "k" is a constant. Problems that have a solution that runs in polynomial time are in the class P. Problems that are in NP have algorithms that run in exponential or factorial time.
However, the fact that a purported solution can be quickly verified or refuted does not require or imply that an answer can be found swiftly. An example of this is the factoring problem. Factoring a number involves finding which other numbers when multiplied together form the original. The factors of ten, for instance are {1,10} and {2,5} because both 1x10 and 2x5 equal 10. Even the best known factoring algorithms have exponential running times, where as the checking algorithm, plain ordinary multiplication, has polynomial running time. Factoring is in the class of NP-Complete problems.
NP-Complete problems are NP problems that have the added qualification that no other NP problem is more than a polynomial factor harder. Informally, a problem is NP-Complete if answers can be verified quickly, and a fast algorithm to solve this problem can be used to solve all other NP problems quickly. There is also much argument among mathematicians as to whether NP=NP-Complete; that is, does the subset NP-Complete comprise all NP problems. If it does and anyone ever finds a polynomial algorithm to solve an NP problem, then it will effectively prove that NP=P.
Although it may seem a bit esoteric and possibly irrelevant, this is extremely important to computer scientists, even if they don't know it. This is because the algorithms that provide most of the world's computer security are based on NP-Complete problems. Therefore, if NP is ever shown to be equal to P, it means that there exist fast algorithms to break this security. And all that remains then is to find them
This is the complete article, containing 480 words
(approx. 2 pages at 300 words per page).
