# How do we know if a problem is hardest in NP

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,

-

## 2 Answers

It all began with the Cook-Levin theorem. The proof of that uses the Turing Machine definition of NP and reduces every problem in NP to SAT.

Any textbook on Computational Complexity will have at least one section devoted to this. I would recommend Papadimitrou's book on Computational Complexity for that. I heard Sipser's book is good too, but I haven't read that.

So to answer your question, yes, one could use (and the above theorem actually does) the Turing Machine to talk about all problems in NP and prove the existence of NP-Hard problems.

-

If every problem, $p$, in a complexity class, $C$, can be reduced to another problem $q$, then $q$ is said to be Hard. (it is not required that $q$ belong to $C$)

You can conclude that if you are able to solve $q$, then you can solve every problem $p$ in $C$ and it must therefore be harder to solve than each problem $p$.

If $q$ is Hard for $C$ and $q$ belongs to $C$, then $q$ is said to be Complete.

If $q$ is Complete, then it means it is one of the most difficult to solve in $C$.

-
I don't think it's the definitions the OP is stuck on, but how to show NP-complete is non-empty. – Douglas S. Stones May 21 '11 at 8:42