Question

Generally, assuming we have a NPC problem. Adding more constraint to it (making it more difficult), is it possible that problem become NPH? I know the difference between NPC and NPH but I don't know how to show that adding new constraints to existing NPC problem will make it NPH or still remains NPC?

Was it helpful?

Solution

Of course can an additional constraint transform an NPC to an NPH problem. Further there could be no person on World able to proof that.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top