Re: NP complete
Hi Waleed ...
A simple minded definition would be like this :
First what NP stands for : Non-deterministic Polynomial which is a generic term in the way the present day turing machine computers solve a given problem.
and NP complete problem is one which has been proved that it cannot be solved using present day computers. Meaning that present day computers may take years or in some cases (depending upon the input numbers), never.
an e.g is the travelling saleman problem (for large number of destination)'
A slightly different class of problems are NP hard problems. These are problems for which no algorithm has been found. But also they have not been proved as unsolvable.
P complete is quite the opposite , a problem proved solvable and an algorithm exists...
hope u got it ....
for details, you can look into books like "Introduction to Computation" by Michael Sipser.... "Introduction to Automata Theory, Languages, and Computation" by Hopcroft-Ullman (addison-wesley) ..
a more specific book on NP completeness wud b "Computers and Intractability: A Guide to NP-Completeness" by Garey and Johnson .... this book has numerous wonderful examples ...
Rgds