NP-complete problem

NP-complete problem

[¦en¦pē kəm′plēt ‚präb·ləm]
(computer science)
One of the hardest problems in class NP, such that, if there are any problems in class NP but not in class P, this is one of them.
References in periodicals archive ?
Solving NP-complete problem using ACO algorithm, In: Emerging Technologies, 2009.
Nevertheless, the NP-complete problems seem to be much harder in the following sense: every algorithm known so far for solving any NP-complete problem requires running times that are exponential, not polynomial, functions of the problem size.
That is, it can be shown that any NP-complete problem can be transformed into each other NP-complete problem by a polynomial-time procedure.
This class is potentially harder to solve than NP-complete problems, because if any NP-complete problem is intractable, then all NP-bard problems are intractable.
SCP is the NP-complete problem of partitioning a given set into mutually independent subsets while minimizing a cost function defined as the sum of the costs associated to each of the eligible subsets.
The Security of RSA Cryptosystein, from the last names of inventors, Rivest, Shamir, and Adleman (1978) depends solely on the lack of existence of a known polynomial time algorithm for factorization of integers, while the security of Diffie & Hellman (1976), ElGamal (1985), and Massey (1988) revolved around the fact that computing the discrete logarithm in finite fields is an NP-complete problem.
On the one hand, we plan to use complexity lower bound techniques as inspiration to design new and improved algorithms for Satisfiability and other NP-complete problems, as well as to analyze existing algorithms better.
DNA computing was introduced by Adleman in 1994 who has explained how to use biological tools to solve NP-Complete problems [1, 8].
The class of NP-Complete problems is a subset of NP problems.
It is one of the most famous NP-Complete problems, and even approximating the chromatic number within an acceptable ratio is NP-hard [7].
Also NP-complete problems, their role in our daily life, and the crucial role in technology in their study, will be discussed.
BAKER, Approximation algorithms for np-complete problems on planar graphs, in Proc.