در نظریه پیچیدگی محاسباتی، یک الگوریتم عددی در شبه چندجمله ای اجرا می شود اگر زمان اجرای اش چندجمله ای در مقدار عددی از ورودی باشد.(که در طول ورودی نمایی است– شماری از رقم هاش).نبومسئله الگوریتم NP کامل با شبه چندجمله ای شناخته شده و به NPکاملِ ضعیف نامیده می شود.مسئله الگوریتم NP کامل اگر ثابت شود که نمی تواند توسط الگوریتم شبه چندجمله ای حل شود، به NP کامل شدید نامیده می شود مگر اینکه P=NP باشد....
