لإثبات أن شيئًا ما هو np-hard ، لماذا تحتاج إلى تقليله من NP-complete؟

Question

من ويكيبيديا:

المشكلة h هي np-hard إذا وفقط إذا كانت هناك مشكلة lp-complete l التي هي وقت متعدد الحدود ، فإنه يمكن تقليله إلى h (أي ، l ≤ th).

لماذا يتم تقليل المشكلة (تسميها W) من الحاجة إلى أن تكون NP-COMPLETE؟ لماذا لا يمكن أن تكون أيضًا NP-Hard؟ يبدو أن ما تهتم به "صعب" وليس في NP.

أفكار؟

Answer 1

يمكن. في الواقع ، فقرتك الثانية تعني الفقرة الأولى.

لنفترض أن مشكلة NP-Hard H هي قابلة للتخفيض متعدد الحدود للمشكلة X. بحكم التعريف ، هناك مشكلة مكتملة NP التي يمكن تقليلها متعدد الحدود إلى H. نظرًا لأن كلا التخفيضات متعددة الحدود ، يمكنك تقليل C إلى X في الوقت متعدد الحدود. لذلك ، فإن مشكلة NP-Complete C قابلة للتقليل إلى X في الوقت متعدد الحدود. لذلك المشكلة x هي np-hard.

Answer 2

إذا تمكنت من تقليل مشكلة NP-HARD لمشكلتك ، فهي تكفي لإثبات عدم وجود مشكلتك في مشكلتك. ومع ذلك ، قد لا تكون مشكلة محددة من NP-HARD قد تكون قابلة للتطبيق متعدد الحدود لمشكلتك على الرغم من أنها NP-HARD نفسها.

علاوة على ذلك ، ليس عليك إثبات صيد NP عن طريق التخفيض ، يمكنك أيضًا إثبات ذلك مباشرة.