If a problem A is NP-Complete and another problem B can be reduced to problem A in polynomial time, what can be said about problem B?यदि कोई समस्या एनपी-पूर्ण है और एक अन्य समस्या बी को बहुपद समय में समस्या के लिए कम किया जा सकता है, तो समस्या बी के बारे में क्या कहा जा सकता है?
यदि कोई समस्या एनपी-पूर्ण है और एक अन्य समस्या बी को बहुपद समय में समस्या के लिए कम किया जा सकता है, तो समस्या बी के बारे में क्या कहा जा सकता है?
Show answerHide answer
Correct answer: (A) Problem B is also NP-Completeसमस्या बी भी एनपी-पूर्ण है
Explanation
Note: the answer key gives (A), but reducing B to an NP-complete A only shows that B is in NP, no harder than A. B is NP-complete only if a known NP-complete problem reduces to B.नोट: आधिकारिक उत्तर कुंजी (A) देती है, लेकिन B को किसी NP-complete A में reduce करने से केवल यह पता चलता है कि B, NP में है और A से कठिन नहीं है। B तभी NP-complete है जब कोई ज्ञात NP-complete समस्या B में reduce हो।