نتایج جستجو

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

...ن مسئله در علوم کامپیوتر ، یک مسئله بهینه سازی کلاسیک است. پس این پرسمان [[ان‌پی سخت|NP-سخت]] است درنتیجه اگر P ≠ NP باشد، نمی توان آن را با یک الگوریتم زما * گراف دوبخشی کامل <math>K_{m,n} </math> دارای پوششی گره‌ای کمینه با اندازه <math>\min(m,n) </ ...

...ترده‌ای را در زمینه‌های ان‌پی-کامل و [[مسئله برابری پی و ان‌پی|برابری پی و ان‌پی]] در پی داشت. از همین روی، کارپ [[جایزه تورینگ]] را در سال [[۱۹۸۵ (میلادی)| [[رده:مسئله‌های ان‌پی کامل]] ...

...بهینه‌سازی، مسئله یافتن بهترین راه حل از میان همه راه حل‌های عملی می‌باشد. مسئله‌های بهینه‌سازی می‌تواند به دو دسته تقسیم شود که متغیرها پیوسته یا گسسته باشند. ...ین و مسائل محاسباتی بهینه‌سازی، مسائل بهینه‌سازی با نسخه‌های تصمیم [[ان‌پی کامل|NP-تکمیل]] لزوماً NPO-تکمیل نامیده نمی‌شوند. ...

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

...یک در [[نظریه پیچیدگی محاسباتی]] و ترکیب شناسیست و یکی از [[۲۱ مسئله ان‌پی-کامل کارپ]] می‌باشد. ...ار داشته باشند. یافتنِ یک پوشش کامل بدون توجه به اندازه آن، یک مسئله ان‌پی کامل می‌باشد. هرچند، اگر ما یک ''مجموعه یکتا'' برای هر عنصرِ S بسازیم و به لیست ...

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

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

...P\neq NP</math>. تحت این فرض، وجود مسائلی درون '''NP''' اما خارج از P و NP-کامل توسط قضیه لادنر اثبات شد.<ref name="Ladner75">R. E. Ladner "On the structur ...زمان چندجمله‌ای به ازای ورودی، ممکن باشد؛ کلاس NP شامل تمام [[مسئله تصمیم|مسئله‌های تصمیم‌گیری]] است که پاسخ‌های مثبت آن‌ها می‌تواند در زمان چندجمله‌ای با اطلا ...

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

...ع این عدد برابر است با تعداد [[دور همیلتونی|دورهای همیلتونی]] در یک [[گراف کامل]] با n رأس. * مسئله معادل در [[نظریه گراف]] به این صورت است که یک [[گراف وزن‌دار]] کامل داریم که می‌خواهیم کم‌وزن‌ترین دور همیلتونی را پیدا کنیم. ...

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

در سال 1975 لوکر ثابت کرد که نوع نامحدود مسئله [[ان‌پی کامل]] است.<ref>{{Cite journal ...نشان داده شد که نوع 0-1 مسئله (برای هر <math>m \ge 2</math> ثابت) [[ان‌پی کامل]] است و به‌طور قویتر FPTAS ندارد مگر اینکه P = NP.<ref>{{cite news|authors ...

...ای جدا کردن این k رأس را بخواهیم این مسئله بازهم یک مسئلهٔ [[ان‌پی کامل|NP کامل]] خواهد شد.<ref>[https://www.jstor.org/stable/3690374?seq=13], which cites< ...عامل ۳ برای هر ''k'' ثابت وجود دارد، به این معنی که یک [[گراف کامل|نمودار کامل]] که [[نابرابری مثلثی|نابرابری مثلث]] را برآورده می‌کند.<ref>{{Harvard cita ...

بزرگترین [[گراف کامل|خوشه]] در [[:en:Permutation graph|گراف جایگشت]]، تعریف می‌شود طولانی‌ترین ز [[رده:مسئله‌های ان‌پی کامل]] ...

...حاصل جمع اعداد این دو زیرمجموعه با هم برابر باشد. اگرچه این مسئله [[ان‌پی کامل]] است اما یک راه‌حل در [[:en:Pseudo-Polynomial time|زمان شبه چندجمله‌ای]] ب [[رده:مسئله‌های ان‌پی کامل]] ...

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

مسئله LCS را می‌توان به زیر مسئله‌های کوچک تر تقسیم نمود. [[رده:مسئله‌های با پیچیدگی زمانی چندجمله‌ای]] ...

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

...on Problem]] از این مسئله و تمام نسخه‌های دیگر استاندارد این مسئله [[ان‌پی کامل]] هستند .این موضوع توسط '''Aggarwal''' و '''D.T.Lee'''و ''' A.K.Lin''' اثبا ...ین هر نقطه داخل مثلث پوشش می‌یابد.تنها نکته‌ای که ممکن در این اثبات به‌طور کامل به آن توجه نشده باشد این است که آیا دوربین می‌تواند در راستای یال را پوشش د ...