تخفيض هو أي نوع من الفكرة؟ ،
يتم تعريف العديد من فئات التعقيد باستخدام مفهوم التخفيض. التخفيض هو تحويل مشكلة إلى مشكلة أخرى. إنه يلتقط الفكرة غير الرسمية لمشكلة تكون على الأقل صعبة مثل مشكلة أخرى. على سبيل المثال، إذا كانت المشكلة X يمكن حلها باستخدام خوارزمية ل Y، فإن X ليست أكثر صعوبة من Y، ونحن نقول أن X يقلل إلى Y. هناك العديد من أنواع مختلفة من التخفيضات، استنادا إلى طريقة التخفيض، مثل تخفيضات كوك، وتخفيضات كارب وتخفيضات ليفين، والحدود على تعقيد التخفيضات، مثل تخفيضات الزمن متعدد الحدود أو تخفيضات المساحة اللوغرافية.