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 ?
We will prove the theorem by reduction from the NP-Complete problem X3C(3).
Multi-Constraint 0-1 Knapsack problem is a NP-complete problem [28], which implies that the computation time it requires to solve this problem is simply infeasible to be implemented in any real systems, and certainly not feasible in a IEEE 802.
Solving NP-complete problem using ACO algorithm, In: Emerging Technologies, 2009.
In order to show its completeness, we give a reduction from the NP-complete problem PARTITION.
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.
Parameterized complexity studies the way in which the hardness of an NP-complete problem depends on the parameter.
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.
To show that U2TD is NP-complete, we will make use of the well-known NP-complete problem 3-SAT [8].
We use a reduction of the following well-known NP-complete problem [GJ79].