(redirected from NP problem)


(NPC, Nondeterministic Polynomial time complete) A set or property of computational decision problems which is a subset of NP (i.e. can be solved by a nondeterministic Turing Machine in polynomial time), with the additional property that it is also NP-hard. Thus a solution for one NP-complete problem would solve all problems in NP. Many (but not all) naturally arising problems in class NP are in fact NP-complete.

There is always a polynomial-time algorithm for transforming an instance of any NP-complete problem into an instance of any other NP-complete problem. So if you could solve one you could solve any other by transforming it to the solved one.

The first problem ever shown to be NP-complete was the satisfiability problem. Another example is Hamilton's problem.

See also computational complexity, halting problem, Co-NP, NP-hard.

References in periodicals archive ?
A decision problem is called an NP problem if particular examples of it can be solved in polynomial time by a nondeterministic process i.
For future work, other NP problems can be solved with genetic algorithms, and new mutations can be obtained by combining two or more types of mutation operators.
First, we shall explain the significance of the P versus NP problem and solve it.
Then since the SUBSET-SUM problem is in class NP but not in class P, we can conclude that P [not equal to] NP, thus solving the P versus NP problem [15].
The P [not equal to] NP problem, the Collatz 3n+1 Conjecture, and the Riemann Hypothesis demonstrate to us that as finite human beings, we are all severely limited in our ability to solve abstract problems and to understand our universe.
To represent the book I've decided to discuss the chapter on the one problem an amateur might have a chance of solving: The P vs NP Problem.
The P vs NP Problem is most likely to be solved by an amateur because unlike any of the other six it is computer based.
Specifically, they are the Riemann hypothesis, which lingers from Hilbert's list, Yang-Mills theory and the mass gap hypothesis, the P Versus NP problem, the Navier-Stokes equations, the Poincaire conjecture, the Birch and Swinnerton-Dyer conjecture, and the Hodge conjecture.
Most people with these NP problems have impairment that does not appear to affect their daily lives; but standard tests can still detect that impairment.
Number of evolutionary algorithms has been proposed for solving NP problems, e.
MC machines were proved to be powerful enough to solve NP problems in less than polynomial time, see [1], [2], [3], [4], [5], [6] and [7]
Two theories will be presented to show how an IP system with IIR can solve NP problems in less steps than normal P system.