در نظریه پیچیدگی محاسباتی، کاهش زمان چندجمله ای روشی برای حل یک مسئله با استفاده از دیگری است. کاهش زمان چند جمله ای اغلب در نظریه پیچیدگی برای تعریف کلاس های پیچیدگی و مسائل کامل برای آن کلاس ها استفاده می شود. …
زمان چند جمله ای در نظر گرفته می شود؟
به یک الگوریتم زمانی چند جمله ای گفته می شود که زمان اجرای آن با یک عبارت چند جمله ای در اندازه ورودی الگوریتم محدود شود، یعنی T(n)=O(nk) برای مقداری ثابت مثبت k.
چگونه می دانید که چیزی یک زمان چند جمله ای است؟
3 پاسخ. یک الگوریتم چند جمله ای است (زمان اجرای چند جمله ای دارد) اگر برای مقداری k، C>0، زمان اجرای آن در ورودی های اندازه n حداکثر Cnk باشد. به طور معادل، یک الگوریتم چند جمله ای است اگر برای برخی از k>0، زمان اجرای آن در ورودی های اندازه n O(nk) باشد.
اگر کاهش در زمان نمایی مجاز باشد چه اتفاقی می افتد؟
اگر کاهش زمان نمایی مجاز باشد، آنگاه می تواند مشکل اصلی را به طور کامل حل کند و یک نمونه بی اهمیت از مسئله هدف تولید کند این به این معنی است که هر مشکل در NP به هر یک قابل کاهش است. مشکل دیگر با چنین نوع کاهش‌هایی است، بنابراین هر مسئله در NP برای کاهش‌های زمان نمایی NP-کامل است.
الگوریتم نمایی چیست؟
به یک الگوریتم زمان نمایی گفته می شود، اگر T(n) با 2 کران بالایی داشته باشدpoly( ) ، که در آن poly(n) چند جمله ای در n است. به طور رسمی تر، یک الگوریتم زمان نمایی است اگر T(n) با O(2nk) برای مقداری k ثابت محدود شود. Ref:Wiki.
