# 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.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.
References in periodicals archive ?
It is considered as a subproblem of the most popular NP-complete problem, the Travelling Salesman Problem (TSP), where the problem is to find the minimum weighted Hamiltonian cycle.
The selection of such disjoint or nondisjoint cover sets is proved to be NP-complete problem [9,11].
As a well-known NP-complete problem, SAT problem has been widely used in artificial intelligence and electronic design automation.
We will prove the theorem by reduction from the NP-Complete problem X3C(3).
The 0/1 knapsack problem has been proved to be an NP-complete problem [21].
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.16m bandwidth request-grant interval where the computation must take place within a few milliseconds.
In 1994 [1] Adleman successfully solved the Direct Hamiltonian Path problem HPP (which is an NP-complete problem) that opens a new area, called DNA computation.
Solving NP-complete problem using ACO algorithm, In: Emerging Technologies, 2009.
There are two significant differences between that undecidable problem and our NP-complete problem: we consider stationary policies and finite horizons.
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.

Site: Follow: Share:
Open / Close