الگوریتم شبه‌چندجمله‌ای
 | این نوشتار نیازمند پیوند میانزبانی است. در صورت وجود، با توجه به خودآموز ترجمه، میانویکی مناسب را به نوشتار بیفزایید. |
 | این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
در نظریه پیچیدگی محاسباتی، یک الگوریتم عددی در شبه چندجمله‌ای اجرا می‌شود اگر زمان اجرای اش چندجمله‌ای در مقدار عددی از ورودی باشد.(که در طول ورودی نمایی است– شماری از رقم هاش).
مسئله الگوریتم NP کامل با شبه چندجمله‌ای شناخته شده و به NPکاملِ ضعیف نامیده می‌شود.مسئله الگوریتم NP کامل اگر ثابت شود که نمی‌تواند توسط الگوریتم شبه چندجمله‌ای حل شود، به NP کامل شدید نامیده می‌شود مگر اینکه P=NP باشد.انواع شدید/ضعیف‌الگوریتم NP-Hardness به طور مشابه تعریف می‌شوند.
مثال[ویرایش]
مسئله‌ای ازتست اینکه آیا n اول هست را در نظر بگیرید، به طور ساده آیا هیچ عددی در{۲، ۳، ...، n/۲} به طور مساوی بر n تقسیم می‌شود.این رویکرد می‌تواند تا n/۲ – ۱ تقسیمات را در بر داشته باشد که در واقع در n خطی است اما نه در اندازه n. برای مثال، عدد ۲٬۰۰۰٬۰۰۰٬۰۰۰ حدود ۱٬۰۰۰٬۰۰۰٬۰۰۰ تقسیمات نیاز دارد، حتی اگر طول n تنها ۱۰رقم باشد.علاوه بر این به راحتی می‌توانید ورودی را بنویسید.(می گویند یک عدد ۳۰۰ رقمی) که برای این الگوریتم غیر عملی است. از آنجا که پیچیدگی محاسباتی مشکل اقدامات با توجه به طول(رمزی)ورودی، این الگوریتم ساده، در واقع نمایی است.با این حال شبه چندجمله‌ای است.
مقایسه این الگوریتم با الگوریتم عددی چندجمله‌ای صحیح می‌گوید، علاوه بر الگوریتم ساده، اضافه کردن ۲ عدد ۹رقمی حدود ۹ مرحله ساده طول می‌کشد و به طور کلی الگوریتم در طول ورودی دقیقاً به صورت خطی است.
در مقایسه با تعداد واقعی که اضافه شده بود(در بیلیون)، الگوریتم می‌تواند به نام شبه لگاریتمی باشد، هر چند چنین واژه‌ای استاندارد نیست.بنابراین، اضافه کردن اعداد ۳۰۰ رقمی غیر عملی نسیت.به طور مشابه بخش طولانی، درجه دوم است، که یک عدد m رقمی می‌تواندتوسط یک عدد n رقمی در رتبه زمانی(O(mn تقسیم شود.
در مورد Primality برای تست اینکه آیا n اول است الگوریتم متفاوتی وجود دارد و آن تولید می‌کند.(در سال ۲۰۰۲ کشف شده‌است) که در زمان (O(log۶n اجرا می‌شود.
مثال دیگری از یک مسئله که می‌تواند به طور کلی فقط با شبه چندجمله‌ای حل شود، مسئله ی کوله پشتی است.
تعمیم به مسائل غیر عددی[ویرایش]
با وجود اینکه مفهومی از شبه چندجمله‌ای تقریباً به طور انحصاری برای مسئله‌های عددی استفاده می‌شود، این مفهوم می‌تواند کلی باشد.تابع m شبه چندجمله‌ای است اگر (m(n از یک تابع چندجمله‌ای از مسئله سایز n و خاصیت اضافی از ورودی (k(n، بزرگتر نباشد.(احتمالاً k انتخاب شده‌است تا یه چیزی مربوط به مسئله باشد).این باعث می‌شود مسئله عددی یک مورد خاص با گرفتن k، تعدادی از اعداد(باینری) از ورودی باشد.
یکی از رمزگذاری، تمایز بین مقدار یک عدد و طولش است اگر ورودی‌های عددی همیشه در unary (یگانه) رمزگذاری شده باشند، سپس شبه چندجمله‌ای همزمان با چندجمله‌ای خواهد شد.
جستارهای وابسته[ویرایش]
- NP کامل شدید
- زمانی شبه چندجمله‌ای
منابع[ویرایش]
- M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company، ۱۹۷۹.