Search code examples
np

If np-complete problems are the hardest problems in np, why are there multiple np-complete problems?


If np-complete problems are the hardest problems in np, why are there multiple np-complete problems?

How can there be multiple hardest problems?

Is it like the top 10 hardest problems hard np-complete?

Are np-complete problems the hardest types of problems?


Solution

  • If np-complete problems are the hardest problems in np.

    The definition of an np-complete problem is: If a problem is NP and all other NP problems are polynomial-time reducible to it, the problem is NP-complete.

    Why are there multiple np-complete problems?

    There are multiple np-complete problems because people have found multiple problems comply with the definition of NP-complete problems.

    How can there be multiple hardest problems?

    There are more problems that are polynomial-time reducible to each other and are NP.

    Is it like the top 10 hardest problems hard np-complete?

    The criterium isn't the top 10 hardest, but they should be NP, and all other NP problems have to be polynomial-time reducible to them.

    Are np-complete problems the hardest types of problems?

    I think that minimally unsolvable problems are harder.