I read that the definition of NP-complete is :    These are the hardest problems in NP. Such a problem is NP-hard and in NPHow do we know if a problem is hardest in NP, and no harder problem exists.I understand that let's assume that somehow magically we know that a problem L is hardest in NP and then we can find out more hardest problems H if we can reduce H to L and vice versa.But my question is how does it all begin? How do we know 1 hardest problem to begin with?Also, to be able to say that something is hardest (or any extreme), we need to know all possible problems in NP and then argue about the hardest.. How do we know all possible NP problems? Is this where turing machine comes useful and by using representation of output string in form of 1 and 0 in output tape, we can theoretically talk about all possible NP problems.I understand that I may not have been able to articulate my question well - due to confusion.Thanks,
How do we know if a problem is hardest in NP
algorithms;efficiency;complexity
You can read about the original 1 hardest problem at http://en.wikipedia.org/wiki/Cook-Levin_theorem.  That includes a sketch of a proof that the problem is, in fact, NP-complete.The problem is Boolean satisfiability.  Given a complicated Boolean expression, can we find a set of inputs that will make it true?  It is easy to see that the problem is in NP (given a possible answer, you just plug it in and evaluate it).  Going the other way is harder.  Here is the basic idea.  Given any problem in NP, you can design a non-deterministic machine that would solve that problem in polynomial time and output a yes or no.  (That is what it means to be in NP.  Note that we can't actually build non-deterministic machines, but we can still theoretically design them.)  Given that machine design we can then design a Boolean expression that is only a polynomial factor larger that will output true/false depending on what the non-deterministic machine would have output.  Therefore if we had a polynomial time algorithm for answering the Boolean satisfiability problem, we could solve any NP problem in polynomial time.Of course once you have one NP-complete problem, we then can go about showing that other NP-problems could be used to solve that one and daisy chain to find other NP-complete problems.  But you have to find one first, and Boolean satisfiability was that first one.