2 ms·
Problems in NP hard that are also in NP are known as NP-complete. NP complete problems share the characteristic that all problems in P can be reduced to any NP
by pdpi 9y ago
Problems in NP hard that are also in NP are known as NP-complete. NP complete problems share the characteristic that all problems in P can be reduced to any NP problem in polynomial time (which is to say: you can encode P problems as particular instances of NP problems). Therefore, if P = NP, all problems in NP are reducible to one another.