علوم رایانشی

علوم رایانشی

معرفی نظام برهان‌های وارسی‌پذیر احتمالی در نظریة پیچیدگی رایانشی و ابهام استفاده از اصطلاح اوراکل در این نظام

نوع مقاله : مروری

نویسندگان
1 دانشجوی کارشناسی ارشد علوم رایانه-محاسبات علمی، دانشکده ریاضی، دانشگاه تحصیلات تکمیلی علوم پایه زنجان، زنجان، ایران
2 استادیار، دانشکده علوم رایانه و فناوری اطلاعات، دانشگاه تحصیلات تکمیلی علوم پایه زنجان، زنجان، ایران
10.22034/csj.2026.555613.1133
چکیده
قضیة برهان‌های وارسی‌پذیر احتمالی، که به اختصار آن را پی‌سی‌پی می‌نامیم، به‌‌منظور اثبات نتایج مربوط به عدم تقریب‌پذیری معرفی شده است. نظام مزبور تعریفی نو از رده‌های پیچیدگی، اعم از P و NP، ارائه نموده و ابزاری قدرتمند جهت واکاوی پرسش‌های بنیادین و حل‌نشده‌ نظریة پیچیدگی محاسباتی فراهم آورده است. مقاله‌ حاضر ابتدا ساختار نظام پی‌سی‌پی را بررسی و معرفی می‌کند و سپس، عدم تقریب‌پذیری الگوریتم‌ها را به‌عنوان یکی از نتایج اصلی قضیة پی‌سی‌پی تبیین می‌نماید. در این میان، «اوراکل» یکی از اصطلاحات کلیدی در حوزة تحقیقاتی پی‌سی‌پی‌ است که در استدلال‌های عدم تقریب‌پذیری کاربرد دارد. اگرچه اوراکل در نظریة محاسبات کلاسیک به‌مثابة جعبه‌سیاهی با توانایی حل مسائل رایانش‌ناپذیر تلقی می‌شود، اما در چارچوب پی‌سی‌پی، این واژه صرفا بیانگر دسترسی تصادفی و آنی به بیت‌های رشتة برهان است. قضیة پی‌سی‌پی بر پایه‌ همین دسترسی کارآمد و مبتنی بر احتمالات استوار است. پژوهش حاضر نشان می‌دهد کاربرد مفهوم اوراکل در حوزة پی‌سی‌پی، تمایزی ماهیتی با ماشین‌های تورینگ مجهز به اوراکل دارد. به‌طور خلاصه، اوراکل در پی‌سی‌پی نه عملیات محاسبه‌ناپذیر، بلکه مدلی انتزاعی از دسترسی به حافظه است؛ حال آن که در مدل‌های فرارایانشی، دلالت بر توانایی‌های فراتر از ماشین تورینگ دارد. بنابراین، خلط این دو مفهوم می‌تواند اعتبار اثبات‌های عدم تقریب‌پذیری را به اشتباه مخدوش سازد.
کلیدواژه‌ها
موضوعات

1.    Arora, S., & Barak, B. 2009. Computational complexity: a modern approach, Cambridge University Press.
2.   Aaronson, S. 2016. ", Open Problems in Mathematics, pp. 1-122, Springer.
3.    Sipser, M. 2012. Introduction to the theory of computation, Wadsworth Publishing.
4.    Sudan, M. 2009. "Probabilistically checkable proofs", Communications of the ACM, Vol. 52, No. 3, pp. 76-84.
5.    Goldreich, O. 2008. "Computational complexity: a conceptual perspective", ACM Sigact News, Vol. 39, No. 3, pp. 35-39.
6.    Arora, S., & Safra, S. 1998. "Probabilistic checking of proofs: A new characterization of NP", Journal of the ACM (JACM), Vol. 45, No. 1, pp. 70-122.
7.    Oreggia, E. M. I. 2013. Towards the Oracle Machine (MPhil Thesis). Goldsmiths College, University of London.
8.    Alper, J. D. 2001. Oracle theory. Oracle Theory Course Notes, Brown University.
9.    Wiedermann, J. 2004. "Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines", Theoretical Computer Science, Vol. 317, No. 1-3, pp. 61-69.
10. Bedregal, B. R. C., & Figueira, S. 2006. "Classical computability and fuzzy Turing machines", Latin American Symposium on Theoretical Informatics, pp. 154-165, Springer.
11. Ord, T., & Kieu, T. D. 2005. "The diagonal method and hypercomputation", The British journal for the philosophy of science, Vol. 56, No. 1, pp. 147-156.
12. Davis, M. 2004. "The Myth of Hypercomputation", Alan Turing: Life and Legacy of a Great Thinker, pp. 195-211, Springer.