Post's Correspondence Problem (PCP)
مشكلة تبدو بريئة وبسيطة (مثل لعبة دومينو)، لكنها **مستحيلة الحل (Undecidable)**.
تستخدم لإثبات استحالة حل مشاكل أخرى لا تتعلق بآلات تورنغ مباشرة (مثل قواعد اللغة).
وصف اللعبة:
لديك مجموعتين من "البلاطات" (Tiles)، كل بلاطة لها جزء علوي وجزء سفلي (مثل الكسر).
المطلوب: هل يمكنك ترتيب البلاطات (مع التكرار) بحيث تكون الكلمة المتكونة في السطر العلوي مطابقة تماماً للكلمة في السطر السفلي؟
النتيجة: لا توجد خوارزمية عامة تستطيع دائماً الإجابة بـ "نعم" أو "لا" لهذه المشكلة.
Complexity Classes: P vs NP
Class P (Polynomial)
المشاكل "السهلة" أو "القابلة للحل عملياً".
- يمكن حلها بواسطة Deterministic TM في وقت حدودي (Polynomial Time).
- أمثلة: الترتيب (Sorting)، البحث (Searching)، أقصر مسار.
- الوقت: $O(n^2), O(n^3), \dots$
Class NP (Nondeterministic Polynomial)
المشاكل التي يمكن "التحقق" من حلها بسرعة.
- يمكن حلها بواسطة Non-deterministic TM في وقت حدودي.
- أو: إذا أعطيتني "حلاً مقترحاً" (Certificate)، يمكنني التأكد من صحته في وقت حدودي (بواسطة DTM).
- أمثلة: سودوكو، جدول الاختبارات، SAT.
NP-Completeness (NPC)
The "Hardest" Problems in NP
المشكلة $L$ تسمى NP-Complete إذا تحقق شرطان:
1. $L \in NP$ (هي نفسها في NP).
2. كل مشكلة أخرى في NP يمكن تحويلها (Reduction) إلى $L$ في وقت حدودي.
مشكلة الإرضاء المنطقي (SAT / Satisfiability) هي أول مشكلة تم إثبات أنها NP-Complete.
"إذا استطعت حل SAT بسرعة، فقد حللت كل مشاكل العالم!"
The Big Question: P vs NP؟
(SAT, TSP)
الشكل المتوقع للعلاقة (بافتراض $P \neq NP$). الـ NP-Complete هي "أصعب" جزء في NP.
Solving vs Verifying
P: سهل الحل (Easy to Solve).
NP: سهل التحقق (Easy to Verify).
مثال: حل الـ Puzzle صعب (NP)، لكن التأكد من أن الصورة مكتملة سهل جداً (P).
Is P inside NP؟
نعم! كل مشكلة يمكن حلها بسرعة (P)، يمكن بالتأكيد التحقق منها بسرعة (NP).
السؤال الكبير هو: هل العكس صحيح؟ هل كل NP هو P؟ (أغلب العلماء يعتقدون لا).