ما الذي يُعرّف المشكلة الصعبة؟ بالنظر إلى السؤال السابق، اكتب السياق الذي يحتوي على الإجابة. يمكن أن تكون من 1 إلى 20 جملة السياق:
هذا يحفز مفهوم مشكلة تكون صعبة لفئة التعقيد. المشكلة X صعبة لفئة من المشاكل C إذا كان يمكن تخفيض كل مشكلة في C إلى X. وبالتالي لا توجد مشكلة في C أصعب من X ، لأن خوارزمية X تسمح لنا بحل أي مشكلة في C. بالطبع ، تعتمد مفهوم المشاكل الصعبة على نوع التخفيض المستخدم. بالنسبة لفئات التعقيد الأكبر من P ، يتم استخدام تخفيضات وقت متعدد الحدود بشكل شائع. على وجه الخصوص، مجموعة المشاكل التي هي صعبة على NP هي مجموعة المشاكل NP-الصعبة.