text: what is an np complete problem ?   a problem is assigned to the np (nondeterministic polynomial time) class if it is solvable in polynomial time by a nondeterministic turing machine.a p-problem (whose solution time is bounded by a polynomial) is always also np. if a problem is known to be np, and a solution to the problem is somehow known, then demonstrating the correctness of the solution can always be reduced to a single p  (polynomial time) verification. if p and np are not equivalent, then the solution of np-problems requires (in the worst case) an exhaustive search.    a problem is said to be np-hard if an algorithm for solving it can be translated into one for solving any other np-problem. it is much easier to show that a problem is np than to show that it is np-hard. a problem which is both np and np-hard is called an np-complete problem.