Domanda

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?

È stato utile?

Soluzione

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.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top