بررسی و مقایسه رابطه کلاس های پیچیدگی p و NP

Publish Year: 1392
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 1,469

This Paper With 6 Page And PDF Format Ready To Download

  • Certificate
  • من نویسنده این مقاله هستم

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این Paper:

شناسه ملی سند علمی:

ELECOM01_048

تاریخ نمایه سازی: 9 تیر 1393

Abstract:

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

Authors

میترا زارع

دانشجوی کارشناسی ارشد، مهندسی کامپیوتر دانشگاه علوم و تحقیقات فارس

امین طوسی

عضو هیئت علمی، دانشگاه علوم و تحقیقات فارس

پیام مبرائی

کارشناس، مهندسی کامپیوتر دانشگاه آزاد اسلامی واحد شیراز

مراجع و منابع این Paper:

لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :
  • J. Edmonds. Paths, trees and OWerS. Canadian Journal of Mathematics, ...
  • G. Cantor. Ueber eine Eigenschaft des Inbegri_es aller reellen algebraischen ...
  • A. Turing. On computable numbers, with an ...
  • application to the Etscheidungs problem. Proceedings of the London Mathematical ...
  • M. Furst, J. Saxe, and M. Sipser. Parity, circuits and ...
  • A. Razborov. Lower bounds On the monotone complexity of some ...
  • A. Razborov. On the method of approximations. In Proceedings of ...
  • A. Razborov and S. Rudich. Natural proofs. Journal of Computer ...
  • A. Haken. The intractability of resolution. Theoretical C omputerSc ience, ...
  • S. Arora. Polynomial time approximation schemes for Euclidean traveling salesman ...
  • M. Goemans and D. Williamson. Improved _ _ and programming. ...
  • نمایش کامل مراجع