مشکل H حداقل به سختی L است، زیرا H می تواند برای حل L مورد استفاده قرار گیرد. ;از آنجا که L ان پی کامل باشد و از این رو سخت ترین در کلاس ان پی است، همچنین مشکل H حداقل به اندازه ان پی سخت است اما H نباید در ان پی باشد و بنابراین نباید یک مشکل تصمیم گیری باشد (اگر هم یک مشکل تصمیم گیری بود نیاز ندارد در ان پی باشد). ;از آنجا که مشکلات ان پی کامل به وسیلهٔ کاهش زمان چندجمله ای به چند به یک (تبدیل چن...
