مسائل Np کامل(Np complete problems)

مسائل P به مسائلی گفته می شود که راه حلی با زمان چند جمله ای دارد و مسائل Np ،مسائلی هستند که پیچیده بوده و راه حل چند جمله ای ندارند،اینگونه مسائل فقط شامل مسائل علوم رایانه نیست و مسائلی از علوم مختلف مانند ریاضیات،زیست شناسی و هواشناسی و هر علمی که نیاز به محاسبه دارد را در بر می گیرد. هرچند که به خاطر پیچیده بودن مسائل سعی شده مطالب ساده تر و قابل درک تر از مقاله ها برداشت شده و در اینجا گنجانده شود و با توجه به رشته خودم مسائل موجود در حوزه رایانه جذابتر بوده و مقاله های در این مورد را تقریبا به طور کامل آورده ام.مسئله P و Np در علوم رایانه مسئله جدیدی نیست و سال های متمادی مخصوصا اواخر قرن گذشته بحث های زیادی روی این مسائل صورت گرفته و مقالات و تحقیقات خارجی زیادی در سایت های معتبر درمورد آنها وجود دارد و یکی از مسائل مهم در این زمینه مسئله تقابل و رویاروییp در مقابل Np است که در این مقاله در صفحات زیادی به آن پرداخته ام . از طرفی ، از آنجا که حوزه ی این مسائل گسترده است ، صدها مقاله با موضوع Np یافتم که در حوزه رایانه نبود و من به خاطر درک اندکم در آن علوم قادر به گنجاندن آنها در تحقیقم نبودم،هرچند که برخی از مطالب این تحقیق نیز تا حدودی سنگین است اما امیدوارم برای خواننده قابل درک و ملموس باشد.

Keywords:

, Proof complexity , Proof search , P versus NP , Propositional logic , Satisfiability , Resolution , Polynomial complexity , Data mining , Universal quantum computing , NP-Complete