نظریه پیچیدگی محاسباتی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز اصلاح پیوند به صفحه ابهام‌زدایی با استفاده از AWB |
جز سوال به سؤال، replaced: سوال ← سؤال (6) با استفاده از AWB |
||
خط ۶:
مواردی هست که میدانیم یک مسئله جواب دارد ولی راه حل و روش حل آن هنوز ارائه نگردیده و گاهی علاوه بر مشکل مذکور حتی با در دست داشتن راه حل، منابع و ابزار لازم جهت پیاده‌سازی آن مسئله را نداریم.
بعد از این نظریه که بیان می‌کند کدام مسائل قابل حل و کدام مسائل غیرقابل حل هستند، این
برای سادگی کار مساله‌ها به کلاس‌هایی تقسیم می‌شوند، طوری که مساله‌های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح [[کلاس‌های پیچیدگی]] خوانده می‌شوند.
خط ۱۹:
== آیا P=NP است؟ ==
برابر بودن مسائل کلاس P دقیقا همان مسائل کلاس NP، یکی از مهم‌ترین
== [[پیچیدگی زمانی]] ==
خط ۴۷:
== نمونه مساله ==
یک مسیر ساده در یک گراف به مسیری اطلاق می‌شود که هیچ راس یا یال تکراری در آن وجودنداشته‌باشد. برای پیاده‌سازی مساله ما به این احتیاج داریم که بتوانیم یک
چرا این مساله NP می‌باشد؟ چون اگر مسیری به شما داده شود، به راحتی می‌توان طول مسیر را مشخص نمود و آن را با k مقایسه کرد. همه این کارها در زمان خطی و صد البته در زمان Polynomial قابل انجام می‌باشد.
اگر چه میدانیم که این مساله آیا در کلاس P می‌باشد یا نه، با این حال روش خاصی برای پیدا کردن مسیری با ویژگی‌های ذکر شده نیز بیان نشده‌است؛ و در حقیقت این مساله جز NP-Completeها می‌باشد، پس می‌توان به این نتیجه نیز رسید که الگوریتمی کارآمد با چنان عملیات وجود ندارد.
| |||