I read that the definition of NP-complete is : These are the hardest problems in NP. Such a problem is NP-hard and in NP
How 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,