What does it mean for a problem to be NP Hard or NP Complete?
In: Mathematics
Say you have a set of puzzles, such as jigsaws, rubix cubes, and brain teasers ( like metal pieces that have to sit together. Ones you are able to complete can go in the P category, and you have a method for completing them, which is your ‘algorithm’. Let’s say you finished a 100 piece jigsaw, which is now in P. You open a 5 million piece jigsaw; you know the algorithm to complete it, it may just take an indefinite amount of time. This is the NP complete class. NP Hard is when you can solve a problem with a harder algorithm, simplifying into an easier algorithm of another NP problem. This could be a brain teaser that might have some elements of a larger rubix cube, so it’s solvable algorithm might be reducable into a rubix cube algorithm.
The main basis for all of these is that a computer would have a very hard time solving certain problems ( travelling salesmen problem, etc.) They could hypothetically be solved, but a computer will have an polynomial running time that is not currently feasible. We put these problems into the P, NP and sub NP categories depending on their complexity.
Latest Answers