ماذا سيحدث لو كانت P تساوي NP؟

العديد من المشكلات التي يُعتقد الآن أنها غير قابلة للحل، من الجدولة المثلى إلى كسر الشفرات التشفيرية، سيكون لها خوارزميات فعالة، ولن يكون فعل إيجاد الحلول أصعب من التحقق منها. ستكون الآثار على التجارة والأمن والعلوم عميقة، وهذا جزء من سبب توقع معظم الخبراء أن P لا تساوي NP.

لماذا يصعب حل المشكلة إلى هذا الحد؟

يتطلب إثبات أن P تساوي NP خوارزمية سريعة لمشكلة NP-كاملة، وهو ما لم يعثر عليه أحد؛ ويتطلب إثبات اختلافهما إظهار أنه لا يمكن وجود مثل هذه الخوارزمية. تُظهر النتائج المتعلقة بالنسبية والبراهين الطبيعية أن التقنيات القياسية غير قادرة بطبيعتها على إثبات الأخيرة، لذا هناك حاجة إلى نهج جديد تمامًا.

مسألة P مقابل NP

تتساءل مسألة P مقابل NP عما إذا كان كل مشكلة يمكن التحقق من حلولها بسرعة يمكن حلها بسرعة أيضًا، وهي المسألة المفتوحة المركزية في علم الحاسوب النظري وواحدة من مسائل الألفية لـ Clay.

اعثر على موضوع باستخدام PaperMindقريبًاFind papers & topics

Tools & resources

تنزيل الشرائح

Learn & explore

فيديوقريبًا

Definition

P هي فئة المشكلات القابلة للحل في زمن متعدد الحدود، وNP هي فئة المشكلات التي يمكن التحقق من حلولها المقترحة في زمن متعدد الحدود؛ تتساءل مسألة P مقابل NP عما إذا كانت هاتان الفئتان متساويتين، وهو ما يتحقق إذا وفقط إذا كانت بعض المشكلات NP-كاملة قابلة للحل في زمن متعدد الحدود.

Scope

يغطي هذا الموضوع الصياغة الرسمية لمسألة P مقابل NP، وتكافؤها مع ما إذا كانت أي مشكلة NP-كاملة (NP-complete) تحتوي على خوارزمية زمن متعدد الحدود (polynomial-time algorithm)، وعواقب أي من الإجابتين، والعوائق مثل النسبية (relativization)، والبراهين الطبيعية (natural proofs)، والجبرية (algebrization) التي أعاقت التقدم، والتخمين الواسع الانتشار بأن الفئات مختلفة.

Core questions

هل إيجاد الحل أصعب جوهريًا من التحقق منه؟
لماذا تعتمد الإجابة على ما إذا كانت أي مشكلة NP-كاملة واحدة تقع ضمن P؟
كيف سيبدو العالم إذا كانت P تساوي NP، وإذا لم تكن كذلك؟
لماذا فشلت عقود من الجهد في حل المسألة؟

Key theories

التكافؤ مع NP-completeness: تتساوى P مع NP إذا وفقط إذا كانت أي مشكلة NP-كاملة تحتوي على خوارزمية زمن متعدد الحدود، وبالتالي فإن السؤال الشامل يختزل إلى قابلية حل مشكلة ملموسة واحدة مثل قابلية الإرضاء (satisfiability).
عوائق الإثبات: تُظهر نتائج النسبية والبراهين الطبيعية والجبرية أن تقنيات الإثبات الرئيسية المعروفة لا يمكنها حسم مسألة P مقابل NP، مما يفسر الصعوبة ويوجه البحث عن طرق جديدة جوهريًا.

Clinical relevance

الافتراض بعدم تساوي P وNP هو الافتراض الأساسي وراء التعامل مع المشكلات الصعبة NP (NP-hard problems) على أنها غير قابلة للحل، ووراء أمن التشفير، حيث أن الحل الفعال لمشكلات NP من شأنه أن يكسر التشفير المستخدم على نطاق واسع؛ إن إثباتًا بناءً بأن P تساوي NP سيحدث تحولًا في مجالات التحسين واللوجستيات والعلوم.

History

صاغ كوك السؤال في عام 1971 إلى جانب NP-completeness، وسرعان ما تم الاعتراف به على أنه أساسي. واجهت المحاولات عبر الحدود الدنيا للدوائر (circuit lower bounds) في الثمانينيات حاجز البراهين الطبيعية الذي حدده رازبوروف وروديتش، وفي عام 2000، أطلق معهد كلاي للرياضيات عليها اسم مشكلة الألفية مع جائزة قدرها مليون دولار.

Debates

هل سيتم حل مسألة P مقابل NP يومًا ما، وما هي الإجابة؟: يخمن معظم الباحثين أن P لا تساوي NP، ولكن لا يوجد إثبات موجود وتقنيات الإثبات المعروفة غير كافية بشكل واضح. تختلف الآراء حول ما إذا كان الحل قريبًا، أو يتطلب رياضيات جديدة جذريًا، أو ما إذا كانت المسألة قد تكون مستقلة عن البديهيات القياسية.

Key figures

Stephen Cook
Leonid Levin
Richard Karp
Alexander Razborov

Seminal works

cook1971
aroraBarak2009

Frequently asked questions

ماذا سيحدث لو كانت P تساوي NP؟: العديد من المشكلات التي يُعتقد الآن أنها غير قابلة للحل، من الجدولة المثلى إلى كسر الشفرات التشفيرية، سيكون لها خوارزميات فعالة، ولن يكون فعل إيجاد الحلول أصعب من التحقق منها. ستكون الآثار على التجارة والأمن والعلوم عميقة، وهذا جزء من سبب توقع معظم الخبراء أن P لا تساوي NP.
لماذا يصعب حل المشكلة إلى هذا الحد؟: يتطلب إثبات أن P تساوي NP خوارزمية سريعة لمشكلة NP-كاملة، وهو ما لم يعثر عليه أحد؛ ويتطلب إثبات اختلافهما إظهار أنه لا يمكن وجود مثل هذه الخوارزمية. تُظهر النتائج المتعلقة بالنسبية والبراهين الطبيعية أن التقنيات القياسية غير قادرة بطبيعتها على إثبات الأخيرة، لذا هناك حاجة إلى نهج جديد تمامًا.