what is NP Complete what use of NP Complete

nahidshahin · Post by **nahidshahin** » Mon Jun 14, 2004 4:35 am

Hello
Can any one explain what is NP Complete.
And what the use of NP Complete.
Thanks

anupam · Post by **anupam** » Mon Jun 14, 2004 8:11 am

Hello nahidshahin,
First of all, I suggest you to read some interesting books of ,p NP.
1. CRLS
2. Sahni
3. Garey & Johnson.(purely Np).

In a word, Np are those problems for which there is no best algorithm or there is no polynomila time algorithm yet to solve them.

There are previous posts. check them.

Alessandro · Post by **Alessandro** » Mon Jun 14, 2004 10:42 pm

Solvable computer problems are classified in several sets.

The NP problems can be "verified" in polynomial time: given the problem and a solution, you can check in polynomial time if it's a valid solution.

The P problems are those NP problems that can also be "solved" in polynomial time.

Otherwise, NP-complete problems can be solved only in superpolynomial time, like n! or 2^n. The NP-completeness of a problem can be proven, so we can know if a certain problem is solvable before trying to solve it.

All the NP-complete problem can be reduced to a single problem defined as NP-complete, the Circuit-Sat. If one NP-complete will be proven to be solvable in polynomial time, all NP-complete problems can be.

Hundreds of problems are NP-complete: 3-coloring, subset sum, vertex cover, TSP, etc...