Advanced Complexity Classes

الفصل الثاني عشر: ما وراء NP-Complete والتعقيد المكاني

الهدف: استكشاف مشاكل NP الشهيرة (TSP, Vertex Cover) وفهم صنف PSPACE.
1

The Tale of Two SATs

مشكلة الإرضاء المنطقي (SAT) لها عدة أشكال، وتغيير بسيط في الشروط يقلب الموازين تماماً.

3SAT (3-Satisfiability)

$(x_1 \lor \bar{x}_2 \lor x_3) \land (x_2 \lor x_4 \lor \bar{x}_1) \dots$
  • الوصف: كل قوس (Clause) يحتوي على 3 متغيرات بالضبط.
  • التصنيف: NP-Complete .
  • السبب: لا توجد طريقة معروفة لحلها سوى التجربة (التي تأخذ وقتاً أسياً).

2SAT (2-Satisfiability)

$(x_1 \lor \bar{x}_2) \land (\bar{x}_1 \lor x_3) \dots$
  • الوصف: كل قوس يحتوي على متغيرين فقط.
  • التصنيف: P (Easy) .
  • السبب: يمكن تحويلها لمشكلة "رسم بياني" (Graph Reachability) وحلها في وقت خطي $O(n)$.
2

Famous NP-Complete Problems

1. Independent Set (IS)

اختر أكبر مجموعة من العقد (Nodes) بحيث لا يوجد أي عقدتين متصلتين ببعضهما.

A
B
C

2. Node (Vertex) Cover (VC)

اختر أقل مجموعة من العقد بحيث تغطي كل الحواف (Edges) في الرسم البياني.

A
B
C
علاقة هامة: لأي رسم بياني بـ $n$ عقد، حجم الـ IS + حجم الـ VC = $n$.
لذلك، يمكن تحويل المشكلتين لبعضهما بسهولة (Reduction).

3. Traveling Salesman Problem (TSP)

لديك مجموعة مدن والمسافات بينها. هل يوجد مسار يزور كل مدينة مرة واحدة ويعود للبداية بمسافة إجمالية $\le k$؟
* هذه المشكلة هي التعميم لمشكلة Hamilton Circuit.

3

Space Complexity (PSPACE)

ما هو PSPACE؟

هو صنف المشاكل التي يمكن حلها باستخدام مساحة ذاكرة (Tape Cells) محدودة بـ كثير حدود (Polynomial) بالنسبة لطول المدخل.
* الوقت (Time) غير محدود، المهم الذاكرة فقط.

P
⊆
NP
⊆
PSPACE

يعتقد العلماء أن $P \ne NP \ne PSPACE$، لكن لم يثبت ذلك أحد!

4

QBF (The King of PSPACE)

ما هي QBF؟

هي تعميم لمشكلة SAT. في SAT نسأل: "هل يوجد قيم للمتغيرات؟" ($\exists$).
في QBF، نستخدم المكممات (Quantifiers): "لكل" ($\forall$) و "يوجد" ($\exists$).

$\forall x \exists y \forall z \dots (x \lor y \land \bar{z} \dots)$
SAT (NP-Complete):
$\exists x_1 \exists x_2 \dots \phi$
(Player 1 moves only).
QBF (PSPACE-Complete):
$\forall x_1 \exists x_2 \forall x_3 \dots \phi$
(Game between 2 players).
🛡️ EXAM VAULT (خزنة الاختبار)
TRAP / فخ

Difference between 2SAT and 3SAT

قد تظن أن 2SAT هي NP-Complete مثل 3SAT، لكنها ليست كذلك.
2SAT تنتمي إلى P ويمكن حلها بكفاءة.
السبب: قيودها تسمح بحلها عبر خوارزميات الرسم البياني (Implication Graph).

THEOREM / نظرية

Savitch's Theorem

تقول النظرية: $NPSPACE = PSPACE$.
بمعنى: الـ Non-determinism لا يضيف قوة عندما يتعلق الأمر بالمساحة (Space)، بعكس الوقت (Time) حيث $P$ قد لا تساوي $NP$.

→ السابق (Ch 11) الفصل التالي (Ch 13) ←