How do we know if a problem is hardest in NP

I read that the definition of NP - full is: These are the hardest troubles in NP. Such a trouble is NP - tough and also in NP

How do we understand if a trouble is hardest in NP, and also no tougher trouble exists. I recognize that allow is think that in some way amazingly we understand that a trouble L is hardest in NP and afterwards we can figure out even more hardest troubles H if we can lower H to L and also vice versa.But my inquiry is just how does it all begin? Just how do we understand 1 hardest trouble to start with?

Additionally, to be able to claim that something is hardest (or any kind of severe), we require to recognize all feasible troubles in NP and afterwards say concerning the hardest. Just how do we understand all feasible NP troubles? Is this where turing equipment comes valuable and also by utilizing depiction of result string in kind of 1 and also 0 in result tape, we can in theory speak about all feasible NP troubles.

I recognize that I might not have actually had the ability to express my inquiry well - as a result of complication.

Many thanks,

2022-06-07 14:33:32
Source Share
Answers: 2

It all started with the Cook-Levin theory. The evidence of that makes use of the Turing Machine definition of NP and also lowers every trouble in NP to SAT.

Any kind of book on Computational Complexity will certainly contend the very least one area committed to this. I would certainly advise Papadimitrou is publication on Computational Complexity for that. I listened to Sipser is publication is excellent also, yet I have not read that.

So to address your inquiry, yes , one can make use of (and also the above theory in fact does) the Turing Machine to speak about all troubles in NP and also confirm the presence of NP - Hard troubles.

2022-06-07 14:52:30

If every trouble, $p$, in an intricacy class, $C$, can be lowered to an additional trouble $q$, after that $q$ is claimed to be Hard . (it is not called for that $q$ come from $C$)

You can end that if you have the ability to address $q$, after that you can address every trouble $p$ in $C$ and also it have to consequently be tougher to address than each trouble $p$.

If $q$ is Hard for $C$ and also $q$ comes from $C$, after that $q$ is claimed to be Complete .

If $q$ is Complete, after that it suggests it is just one of one of the most hard to address in $C$.

2022-06-07 14:52:23