نتایج جستجو

...[[ابرگراف]] یک‌شکل است. پیدا کردن بزرگ‌ترین تطابق سه‌بعدی یک مسئلۀ [[ان‌پی-سخت]] مشهور در [[نظریه پیچیدگی محاسباتی]] است. ...د دارد؟ این مسئلۀ تصمیم [[ان پی (کامل)|ان‌پی-کامل]] است؛ یکی از [[۲۱ مسئله ان‌پی-کامل کارپ]] است. ...

...وم کامپیوتر ، یک مسئله بهینه سازی کلاسیک است. پس این پرسمان [[ان‌پی سخت|NP-سخت]] است درنتیجه اگر P ≠ NP باشد، نمی توان آن را با یک الگوریتم زمان چند جمله ...هٔ [[ان‌پی کامل]] و یکی از پرسمان‌های [[۲۱ مسئله ان‌پی-کامل کارپ|۲۱ پرسمان ان‌پی-کامل کارپ]] است. ...

...بهینه‌سازی، مسئله یافتن بهترین راه حل از میان همه راه حل‌های عملی می‌باشد. مسئله‌های بهینه‌سازی می‌تواند به دو دسته تقسیم شود که متغیرها پیوسته یا گسسته باشند. در زمینه الگوریتم‌های تخمین، الگوریتم‌ها برای مسائل سخت برای یافتن راه حل‌های نزدیک بهینه طراحی می‌شوند؛ بنابراین یک نسخه معمول تصم ...

...تانه (به لزوم) بیشینه نیست. یافتن مجموعهٔ ناوابستهٔ بیشینه پرسمانی [[ان‌پی سخت]] است. از این روی نمی‌توان در زمانی کوتاه چنین مجموعه‌ای را یافت. ...ر گراف و [[علوم رایانه|علم کامپیوتر]] کاربردهای بسیاری دارد و حتی جزء دسته مسئله‌های [[نظریه پیچیدگی محاسباتی#.D9.85.D8.B9.D8.B1.D9.81.DB.8C NP-Complete|NP-comp ...

...] کلاسیک در [[نظریه پیچیدگی محاسباتی]] و ترکیب شناسیست و یکی از [[۲۱ مسئله ان‌پی-کامل کارپ]] می‌باشد. ...، حتی با وجود سخت بودن یافتن بعضی از kها، پیدا کردن یک k برای یک ورودی خاص سخت نیست! برای مثال، ما می‌توانیم از [[الگوریتم حریصانه]] استفاده کنیم که دنبال ...

...ی]]، کلاس P یکی از پایه‌ترین [[کلاس‌های پیچیدگی]] است. این کلاس، شامل همهٔ مسئله‌های تصمیمی است که می‌توانند با استفاده از [[پیچیدگی زمانی]] [[چندجمله‌ای]]، با کلاس عمومی تر کلاس پی، NP نام دارد که کلاسی از مسئله‌های تصمیم است ک به کمک ماشین تورینگ ناپایستار که در زمان چندجمله‌ای اجرا می‌شود ...

...یم‌گیری متناظر آن، مسئله NP کامل پوشش مجموعه را تعمیم می‌دهد و در نتیجه NP سخت است. [[الگوریتم تقریبی]] که برای اداره کردن مسئله پوشش راس ارائه شد، در این مسئله پوشش مجموعه، انتزاع بسیاری از مسئله‌های ترکیبی است. به عنوان مثال ساده، فرض کنید X مجموعه‌ای از مهارت‌های مورد نیاز ...

مسئله فروشنده دوره‌گرد جزء مسائل [[ان‌پی سخت]] است. راه‌های معمول مقابله با چنین مسائلی عبارتند از: * پیدا کردن زیرمسئله‌هایی از مسئله یا به عبارت دیگر تقسیم مسئله به مسئله‌های کوچکتر، تا بتوان الگوریتم‌های جستجوی بهتر و دقیق‌تری ارائه داد. ...

...زمان چندجمله‌ای به ازای ورودی، ممکن باشد؛ کلاس NP شامل تمام [[مسئله تصمیم|مسئله‌های تصمیم‌گیری]] است که پاسخ‌های مثبت آن‌ها می‌تواند در زمان چندجمله‌ای با اطلا == [[ان‌پی کامل]] == ...

...د [[ان‌پی کامل]] است. مجموعه گره بازخورد یکی از ۲۱ پرسشی است که [[۲۱ مسئله ان‌پی-کامل کارپ|کارپ]] پیچیدگی رایانشی‌شان را بررسی کرده‌است. مجموعه گره‌های بازخ ...‌های بدون جهت ذکر می‌کند،جایی که مسئله روی گراف‌هایی از بیشینه درجه 4 ،NP سخت باقی می‌ماند.مسئله مجموعه گره بازخورد می‌تواند در زمان چندجمله‌ای روی گراف‌ ...

...چه بهینه و چه تقریبی). به همین دلیل این مسئله به عنوان "'''ساده‌ترین مسئله سخت'''" شناخته شده‌است. == نمونه‌های سخت == ...

مسئله پوشش بیشینه یک [[ان‌پی سخت]] (به انگلیسی: NP-hard) و نمی‌تواند تحت مفروضات [[استاندارد]] با <math>1 - [[رده:مسئله‌های ان‌پی کامل]] ...

پرسمان صدق‌پذیری نخستین پرسمانی است که [[ان‌پی کامل]] بودنش نشان داده شده‌است. [[قضیه کوک لوین|کوک و لوین]] نشان دادند الگ ...ادیر منطقی داد تا فرمول همواره درست باشد. [[مسئلهٔ صدق‌پذیری دودویی]] یک [[ان‌پی کامل]] است. مسئلهٔ صدق‌پذیری گزاره‌ای (PSAT)، که مشخص می‌کند آیا یک [[فرمول ...

در [[نظریه گراف]]، '''رنگ‌آمیزی گراف''' یکی از حالت‌های خاص مسئله‌های [[برچسب‌گذاری گراف]] است. رویکرد کلی آن استفاده از نظیر کردن رنگهایی به یال ...‌های مختلفی روی نوع گرافها، روی روش رنگ‌آمیزی و حتی تعداد و رنگ عناصر گراف مسئله‌های متنوعی با کاربردهای وسیع در صنعت و علوم تعریف و حل می‌شود. با وجود اینکه ای ...

برای سادگی کار مسئله‌ها به کلاس‌هایی تقسیم می‌شوند، طوری که مسئله‌های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اص البته کلاس‌های پیچیدگی به مراتب سخت‌تری از '''NP''' نیز وجود دارند. ...

...ح توسط [[Fanya Montalvo]] به تقلید از [[ان‌پی کامل|NP-Complete]] و [[ان‌پی سخت|NP-Hard]] در [[نظریه پیچیدگی محاسباتی|نظریه پیچیدگی]]، که به طور رسمی معروف [[رده:مسئله‌های محاسباتی]] ...

...تن کوچکترین مجموعهٔ غالب یال‌هاست. هر دوی این مسائل [[بهینه‌سازی]] [[ان‌پی-سخت]] است. نسخه‌های [[تصمیم گیری]] از این مسائل، از جمله مثال‌های کلاسیک مسائل [[رده:مسئله‌های با پیچیدگی زمانی چندجمله‌ای]] ...

...ام می‌شود. گرچه [[مسیر همیلتونی|مسئلهٔ مسیر همیلتونی]] به‌طور کلّی [[ان‌پی سخت]] است، امّا در بسیاری از گراف‌ها این شیوهٔ ابتکاری قادر است یک راه حل در [[ [[رده:مسئله‌های ریاضی]] ...

...math>Y(G)</math> کوچک‌تر از <math>K \in \mathbb{R}</math> مسئله ای [[ان‌پی سخت]] است {{harvtxt|Grandoni|2006}}. بنابراین تاکنون الگوریتم بهینه‌ای برای یاف [[رده:مسئله‌های ان‌پی کامل]] ...

معمولاً مسئله افراز گراف در رده مسائل NP-سخت قرار می‌گیرد. راه حل این مسائل به صورت کلی از طریق روش‌های مکاشفه‌ای و تقری از آنجایی که افراز گراف جزو مسائل سخت است، راه حل‌های عملی آن از روش‌های مکاشفه‌ای به دست آمده‌اند. دو گروه گسترد ...