إذا كتبت يوماً برنامجاً يوزع مناوبات الموظفين أو يرتب مسار مندوب توصيل يمر على عشر نقاط، فربما جربت الطريقة الأولى التي تخطر على بال أي مبرمج: جرب كل الاحتمالات واختر الأفضل. ومع عشر نقاط ينتهي البرنامج في ثانية، ثم يضيف المدير نقطتين فينتظر دقيقتين، ثم يضيف ثلاثاً أخرى فلا ينتهي البرنامج قبل نهاية الدوام. وربما رأيت أيضاً المحرر Editor يحذرك أن سطراً «قد لا يصل إليه التنفيذ أبداً» ثم يخطئ، أو أن متغيراً «قد يستخدم قبل أن يعطى قيمة» وهو ليس كذلك، فتسأل: لماذا لا تستطيع هذه الأدوات الذكية أن تعرف بالضبط ماذا سوف يفعل البرنامج؟
هذان السؤالان يقودان إلى أعمق نتيجتين في علوم الحاسب. الأولى أن هناك أسئلة لا يستطيع أي برنامج أن يجيب عنها إطلاقاً، مهما كان الجهاز سريعاً والوقت طويلاً، وأشهرها مشكلة التوقف Halting Problem. والثانية أن هناك مسائل يمكن حلها نظرياً، ولكن كل الطرق المعروفة لحلها تنفجر في الوقت مع حجم المدخل، وهذا هو سؤال P مقابل NP الذي ما زال مفتوحاً منذ أكثر من خمسين سنة. وفي هذا المقال لن نكتفي بالتعريفات، وإنما سوف نكتب البرهان على مشكلة التوقف ككود يعمل، ثم نقيس بأيدينا كيف ينفجر وقت حل مسألة SAT ومسألة البائع المتجول.
وسوف نناقش في هذا المقال ما يلي:
- من أين جاء سؤال «ما الذي يمكن حسابه؟»، ومن هو Alan Turing في هذه القصة.
- مشكلة التوقف، والبرهان بالقطر Diagonal Argument مكتوباً بلغة Python ومشغلاً ضد ثلاثة برامج تحاول حلها.
- الفرق بين المسائل القابلة للحسم Decidable وغير القابلة للحسم Undecidable، وأثر ذلك على أدوات التحليل التي تستخدمها كل يوم.
- لماذا لا ينقذنا أن ذاكرة الحاسب الحقيقي محدودة.
- من القابلية إلى الكلفة: الصنف P والصنف NP والمسائل NP-Complete.
- مختبر SAT: البحث الشامل مقابل خوارزمية DPLL، ولماذا التحقق من الحل سريع والبحث عنه بطيء، وأين تقع الصيغ الصعبة.
- مختبر البائع المتجول TSP: كل الترتيبات، ثم البرمجة الديناميكية، ثم حل تقريبي سريع وكم يبعد عن الأفضل.
- ماذا تفعل عملياً عندما تواجه مسألة من هذا النوع، والأخطاء الشائعة.
من أين جاء سؤال «ما الذي يمكن حسابه؟» Computability
في 1928 طرح الرياضي الألماني David Hilbert مع Wilhelm Ackermann سؤالاً عرف باسم «مسألة القرار» Entscheidungsproblem: هل توجد طريقة آلية، أي خطوات محددة يمكن أن ينفذها شخص دون تفكير، تقرر لأي عبارة رياضية منطقية هل هي صحيحة أم لا؟ وكان الأمل أن تكون الإجابة نعم، فتصبح الرياضيات كلها قابلة للحساب. والمشكلة أن أحداً لم يكن يملك تعريفاً دقيقاً لمعنى «طريقة آلية» حتى يثبت وجودها أو عدمها.
وفي 1936 نشر Alan Turing، وعمره 24 سنة، ورقته On Computable Numbers, with an Application to the Entscheidungsproblem، وفيها عرف «الطريقة الآلية» بآلة خيالية بسيطة جداً: شريط طويل مقسم إلى خانات، ورأس يقرأ خانة ويكتب فيها ويتحرك يميناً أو يساراً، وجدول قواعد صغير يقول للرأس ماذا يفعل في كل حالة. وهذه هي آلة تورنغ Turing Machine، والفكرة المهمة فيها أن كل ما يستطيع أي حاسب اليوم أن يحسبه، من هاتفك إلى أكبر سيرفر، تستطيع آلة تورنغ أن تحسبه، ببطء أكبر فقط. وقد مررنا على قصة Turing في مقال قصة الذكاء الاصطناعي من تورنغ إلى ChatGPT، وإذا كنت قد بنيت مفسراً صغيراً في مقال ابن مفسراً صغيراً بيدك فأنت تعرف الإحساس: برنامج يقرأ برنامجاً آخر وينفذه خطوة خطوة.
وفي نفس السنة تقريباً وصل الرياضي الأمريكي Alonzo Church إلى نفس النتيجة بطريقة مختلفة تماماً، هي حساب لامدا Lambda Calculus الذي صار لاحقاً أساس البرمجة الوظيفية Functional Programming. وتبين أن الطريقتين متكافئتان، أي أن كل ما يحسب بإحداهما يحسب بالأخرى، ومن هنا جاءت الفكرة المعروفة بأطروحة Church وTuring: كل ما نعتبره «قابلاً للحساب بطريقة آلية» هو بالضبط ما تحسبه آلة تورنغ. وهي أطروحة وليست مبرهنة، لأن «الطريقة الآلية» مفهوم بشري لا يمكن تعريفه رياضياً إلا بأحد هذين النموذجين، ولكن لم يجد أحد حتى اليوم طريقة حساب تتجاوزهما، ولا حتى الحاسب الكمومي، الذي قد يكون أسرع في مسائل معينة، ولكنه لا يحسب ما لا تحسبه آلة تورنغ.
وبهذا التعريف استطاع Turing أن يثبت أن الإجابة عن سؤال Hilbert هي «لا»، وكانت أداته في ذلك سؤالاً يبدو أبسط بكثير، وهو مشكلة التوقف.

مشكلة التوقف Halting Problem: سؤال يبدو سهلاً
السؤال كما يلي: أعطني أي برنامج وأي مدخل له، وأنا أخبرك هل سوف يتوقف هذا البرنامج يوماً ما، أم سوف يدور إلى الأبد. ويبدو هذا سؤالاً عملياً جداً، فلو وجد برنامج يجيب عنه، لأضافه كل محرر وكل خط CI لينبهك قبل أن تنشر كوداً فيه حلقة لا تنتهي.
والحل الأول الذي يخطر على البال: شغل البرنامج وانتظر. فإذا توقف فالإجابة «نعم». والمشكلة في الحالة الأخرى، فإذا لم يتوقف بعد دقيقة، فهل هو في حلقة لا نهائية، أم أنه برنامج بطيء سوف ينتهي بعد ساعة؟ ولا يوجد وقت انتظار يكفي لكل البرامج. والحل الثاني: اقرأ الكود وابحث عن الحلقات التي لا تنتهي، مثل while True دون break. وهذا يكتشف الحالات الواضحة، ولكن شرط توقف الحلقة قد يعتمد على حساب لا يعرف أحد نتيجته. فمثلاً لا يعرف أحد حتى اليوم هل الحلقة التالية تتوقف لكل رقم موجب n، وهي ما يسمى حدسية Collatz:
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1ولكن عدم معرفتنا بطريقة لا يعني أنها غير موجودة، وهنا يأتي برهان Turing، الذي يقول إنه لا يمكن أن يوجد برنامج واحد يجيب عن السؤال إجابة صحيحة لكل البرامج، والدليل أن أي برنامج تدعي أنه يفعل ذلك يمكن أن نبني له برنامجاً يخدعه.
البرهان بالقطر Diagonal Argument ككود يعمل
الفكرة كما يلي: لنفرض أن لديك دالة halts(p, x) تجيب دائماً وبشكل صحيح: هل يتوقف البرنامج p عندما نعطيه المدخل x؟ الآن نكتب برنامجاً «معاكساً» Contrarian يأخذ برنامجاً p ويسأل halts عن p عندما يعطى نفسه كمدخل، ثم يفعل العكس: إذا كانت الإجابة «سوف يتوقف» دخل في حلقة لا تنتهي، وإذا كانت «لن يتوقف» توقف فوراً. ثم نعطي البرنامج المعاكس نفسه. فإذا قالت halts إنه يتوقف، فهو لن يتوقف، وإذا قالت إنه لن يتوقف، فهو يتوقف. أي أن halts مخطئة في الحالتين، وهذا يناقض الفرض أنها صحيحة دائماً.
ولماذا يسمى «بالقطر»؟ تخيل جدولاً، صفوفه كل البرامج الممكنة وأعمدته كل المدخلات الممكنة، وفي كل خانة «يتوقف» أو «لا يتوقف». والبرنامج المعاكس مصمم بحيث يختلف عن كل برنامج في الجدول في خانة واحدة على الأقل، وهي الخانة التي يعطى فيها البرنامج نفسه، أي خانات القطر. فلا يمكن أن يكون البرنامج المعاكس صفاً في الجدول، ومع ذلك هو برنامج حقيقي، فالجدول الذي تحسبه halts لا يمكن أن يكون كاملاً. وهي نفس الحيلة التي استخدمها Georg Cantor قبل ذلك بعقود ليثبت أن الأعداد الحقيقية لا يمكن عدها.

والبرهان عادة يكتب على الورق بدالة halts مفترضة، ولكننا نستطيع أن نفعل شيئاً أكثر إقناعاً: أن نكتب عدة دوال halts حقيقية بطرق مختلفة، ثم نبني لكل منها برنامجها المعاكس، ونشغله فعلاً لنرى أنها تخطئ. وحتى نستطيع أن «نشغل البرنامج لعدد محدد من الخطوات»، كتبنا البرامج كدوال مولدة Generators في Python، كل yield فيها خطوة واحدة، والبرنامج يتوقف عندما تنتهي الدالة، كما يشرح توثيق Python. والملف halting.py كاملاً في مجلد lab مع المقال، وأهم أجزائه:
def run(prog, arg, budget):
"""Run prog(arg) for at most `budget` steps. Returns the number of steps if it halted, None otherwise."""
g = prog(arg)
for step in range(budget):
try:
next(g)
except StopIteration:
return step
return None
def make_contrarian(decider):
def contrarian(p):
if decider(p, p): # "you say p halts on itself?"
while True: # then loop forever
yield
yield # otherwise stop right away
return contrarianوكتبنا ثلاث دوال تحاول الإجابة عن سؤال التوقف، وكل منها تمثل طريقة حقيقية:
always_yes: تقول «يتوقف» دائماً. وهي ليست غبية كما تبدو، فأغلب البرامج التي يكتبها الناس تتوقف فعلاً.looks_at_source: تحليل ثابت Static Analysis، تقرأ الكود بالوحدة ast وتبحث عنwhile Trueليس فيهاbreakأوreturn، فإذا وجدتها قالت «لا يتوقف». وهذه فكرة كثير من أدوات التحليل.simulate: محاكاة Simulation، تشغل البرنامج حتى 100,000 خطوة، فإذا انتهى قالت «يتوقف»، وإلا قالت «لا يتوقف». ولأن البرنامج المعاكس يستدعي الدالة نفسها، فهي سوف تحاكي نفسها وهي تحاكي نفسها، لذلك أضفنا حداً للعمق، فإذا تجاوز العمق ثلاثة مستويات «خمنت» الإجابة، ونسخةsimulate_guess_yesتخمن «يتوقف» بدلاً من «لا يتوقف».
وشغلنا الملف داخل Container من debian:trixie-slim مع Python 3.13.5، والمخرج سوف يكون كما يلي:
easy programs:
always_yes counts_to_ten -> True spins -> True
looks_at_source counts_to_ten -> True spins -> False
simulate counts_to_ten -> True spins -> False
the contrarian built against each decider:
always_yes says halts=True reality: still running after 1,000,000 steps -> WRONG
looks_at_source says halts=False reality: halted after 1 steps -> WRONG
simulate says halts=True reality: still running after 1,000,000 steps -> WRONG
simulate_guess_yes says halts=False reality: halted after 1 steps -> WRONGولنقرأ المخرج سطراً سطراً:
- الجزء الأول اختبار على برنامجين سهلين:
counts_to_tenيعد إلى عشرة ويتوقف، وspinsيدور إلى الأبد. الدالتانlooks_at_sourceوsimulateأجابتا إجابة صحيحة على الاثنين، وalways_yesأخطأت فيspinsكما هو متوقع. أي أن الدوال ليست سيئة، وهي تعمل في الحالات العادية. always_yesقالت إن برنامجها المعاكس يتوقف، فدخل البرنامج في الحلقة ولم يتوقف بعد مليون خطوة.looks_at_sourceوجدتwhile Trueدونbreakفي كود البرنامج المعاكس، فقالت «لا يتوقف»، ولكن الحلقة لا تنفذ إلا إذا قالت الدالة «يتوقف»، فتوقف البرنامج بعد خطوة واحدة.simulateقالت «يتوقف»، والسبب أن التخمين في أعمق مستوى قلب الإجابة في كل مستوى فوقه، حتى وصلت إلى المستوى الأعلى «يتوقف»، فدار البرنامج المعاكس إلى الأبد.- وعندما غيرنا التخمين في
simulate_guess_yesانقلبت الإجابة، وأخطأت مرة أخرى بالعكس.

ولاحظ ما يقوله هذا المخرج وما لا يقوله: هو لا يثبت أن مشكلة التوقف غير قابلة للحل، فالإثبات هو البرهان المنطقي الذي يعمل لكل دالة ممكنة، وليس لأربع دوال جربناها. ولكنه يبين لك آلية البرهان بشكل ملموس: مهما كانت طريقتك، فإن البرنامج المعاكس يقرأ إجابتك ثم يفعل عكسها، ولا توجد طريقة تفلت من ذلك، لأن البرنامج المعاكس مبني من الدالة نفسها.
ولكن حاسبي محدود الذاكرة Finite Memory، أليس كذلك؟
قد يعترض أحدهم اعتراضاً ذكياً: آلة تورنغ لها شريط لا نهائي، أما الجهاز الحقيقي فذاكرته محدودة، والبرنامج الذي يعمل في ذاكرة محدودة له عدد محدود من الحالات الممكنة، فإذا تكررت حالة فهو في حلقة لا تنتهي، وإذا لم تتكرر فلا بد أن يتوقف يوماً. وهذا صحيح نظرياً، فمشكلة التوقف لآلة ذاكرتها محدودة قابلة للحسم. ولكن انظر إلى العدد: برنامج صغير يستخدم كيلوبايت واحداً فقط من الذاكرة، أي 8,192 بت، له 28192 حالة ممكنة، وهو رقم من قرابة 2,466 خانة عشرية، أكبر بما لا يقارن من عدد الذرات في الكون المرئي. لذلك فإن الحل «النظري» هنا لا يختلف عملياً عن الاستحالة، والنتيجة الهندسية واحدة: لا تتوقع أن تعرف مسبقاً هل البرنامج سوف ينتهي، وضع له حداً.
ولاحظ أن هذا الاعتراض يقودنا مباشرة إلى موضوع النصف الثاني من المقال: الفرق بين «ممكن من حيث المبدأ» و«ممكن في وقت معقول». فمسألة يمكن حلها بتجربة كل الحالات، وعدد الحالات أسي، هي مسألة لا يمكن حلها عملياً، حتى لو كانت قابلة للحسم.
قابل للحسم Decidable أم غير قابل للحسم Undecidable؟
المسألة القابلة للحسم Decidable هي مسألة إجابتها نعم أو لا، ويوجد برنامج يتوقف دائماً ويعطي الإجابة الصحيحة لكل مدخل، مثل «هل هذا الرقم أولي؟» أو «هل يوجد مسار بين هاتين النقطتين في هذا الرسم البياني؟». وغير القابلة للحسم Undecidable هي التي لا يوجد لها مثل هذا البرنامج، ومشكلة التوقف أولها وأشهرها.
والأخطر لنا كمبرمجين هو ما يترتب على ذلك، وهو ما يعرف بمبرهنة Rice: أي خاصية «سلوكية» غير تافهة للبرامج، أي خاصية تتعلق بما يفعله البرنامج وليس بشكل كوده، هي غير قابلة للحسم. فلا يوجد برنامج يقرر بشكل صحيح دائماً هل هذا البرنامج يطبع كلمة معينة، أو هل يصل التنفيذ إلى هذا السطر، أو هل يقرأ هذا المتغير قبل أن يعطى قيمة، أو هل هذا الملف التنفيذي برنامج خبيث. لأنك لو استطعت أن تقرر أي واحدة منها، لاستطعت أن تقرر مشكلة التوقف عبر حيلة بسيطة: أضف السلوك المسؤول عنه في نهاية البرنامج، فيظهر السلوك إذا وفقط إذا توقف البرنامج.
وهذا يفسر السؤال في أول المقال: أدوات التحليل الثابت، من المحرر إلى المترجم إلى أدوات فحص الأمان، لا تستطيع أن تكون دقيقة دائماً، فهي تختار جهة الخطأ. فبعضها متحفظ Conservative، يحذرك من كل ما قد يكون خطأ فيعطيك تحذيرات خاطئة False Positives، كالمترجم الذي يقول إن المتغير «قد يستخدم قبل أن يعطى قيمة» وهو ليس كذلك. وبعضها متساهل، لا يحذرك إلا مما هو متأكد منه فيفوته بعض الأخطاء False Negatives. ولا يوجد خيار ثالث يجمع الدقة الكاملة في الجهتين، وهذه ليست مشكلة في جودة الأداة، وإنما حد رياضي.
والحل الهندسي الذي تستخدمه كل يوم دون أن تفكر فيه هو المهلة Timeout. فبما أنك لا تستطيع أن تعرف مسبقاً هل الطلب سوف ينتهي، فأنت تحدد وقتاً، وبعده تقطع الطلب وتعامله كفشل. وهذا بالضبط ما فعلته دالة simulate بميزانية الخطوات، مع قبول أنها سوف تخطئ أحياناً مع برنامج بطيء. وقد ناقشنا المهلة في الأنظمة الموزعة في مقال كيف تمنع خدمة بطيئة من إسقاط نظامك.
من القابلية إلى الكلفة: التعقيد Complexity
الآن نترك المسائل المستحيلة، وننتقل إلى المسائل الممكنة، ونسأل سؤالاً مختلفاً: كم يكلف الحل؟ وقد شرحنا في مقال الخوارزميات وتعقيد Big-O كيف نصف نمو الوقت مع حجم المدخل. وهنا يهمنا فرق واحد كبير: الفرق بين النمو متعدد الحدود Polynomial، مثل n² وn³، والنمو الأسي Exponential، مثل 2ⁿ وn!. والجدول التالي يبين الفرق بأرقام محسوبة، مع افتراض جهاز ينفذ مليار خطوة في الثانية:
| n | n² | n³ | 2ⁿ | n! |
|---|---|---|---|---|
| 10 | 100 | 1,000 | 1,024 | 3,628,800 |
| 20 | 400 | 8,000 | 1,048,576 (ميلي ثانية) | 2.4 × 10¹⁸ (قرابة 77 سنة) |
| 30 | 900 | 27,000 | 1.07 × 10⁹ (ثانية) | 2.7 × 10³² |
| 50 | 2,500 | 125,000 | 1.1 × 10¹⁵ (13 يوماً) | 3.0 × 10⁶⁴ |
| 100 | 10,000 | 1,000,000 | 1.3 × 10³⁰ (4 × 10¹³ سنة) | 9.3 × 10¹⁵⁷ |
لاحظ أن n³ عند مئة عنصر ما زال مليون خطوة، أي ميلي ثانية، بينما 2ⁿ عند نفس الحجم يحتاج أكثر من عمر الكون بآلاف المرات. ولهذا يعامل علماء الحاسب المسائل التي لها حل متعدد الحدود على أنها «سهلة» حتى لو كان الحل بطيئاً عملياً، ويعاملون المسائل التي لا يعرف لها إلا حل أسي على أنها «صعبة»، لأن الأجهزة الأسرع لا تنقذك: جهاز أسرع بألف مرة يضيف عشرة عناصر فقط إلى ما تستطيع حله بطريقة 2ⁿ.

الصنف P والصنف NP: الحل مقابل التحقق
الصنف P هو كل مسائل نعم أو لا التي يوجد لها حل في وقت متعدد الحدود، مثل ترتيب قائمة، أو إيجاد أقصر طريق في خريطة بخوارزمية Dijkstra، أو معرفة هل الرقم أولي. والصنف NP هو كل المسائل التي إذا أعطاك أحد حلاً مقترحاً، تستطيع أن تتحقق من صحته في وقت متعدد الحدود. وهنا الفكرة كلها، وصفحة معهد Clay للرياضيات تلخصها في سؤال واحد: إذا كان من السهل التحقق من أن الحل صحيح، فهل من السهل أيضاً إيجاد الحل؟
ومثال من الحياة: جدول مناوبات لخمسين موظفاً مع قيود الإجازات والراحة بين المناوبات والمهارات المطلوبة في كل مناوبة. إذا أعطاك أحد جدولاً جاهزاً، فالتحقق منه سهل، تمر على كل قيد وتتأكد أنه محترم. أما إيجاد الجدول من الصفر فقد يحتاج تجربة عدد هائل من الاحتمالات. وكل مسألة في P هي أيضاً في NP، لأنك إذا استطعت أن تحل المسألة بسرعة فأنت تستطيع أن تتحقق من أي حل بأن تحلها وتقارن. والسؤال المفتوح هو العكس: هل كل مسألة يمكن التحقق منها بسرعة يمكن أيضاً حلها بسرعة؟ وهذا هو سؤال P = NP، وهو واحد من سبع مسائل خصص لها معهد Clay جائزة مليون دولار لكل منها، ولم يحله أحد حتى اليوم.
المسائل NP-Complete: إذا حللت واحدة حللت الكل
في 1971 نشر Stephen Cook ورقة The Complexity of Theorem-Proving Procedures، وأثبت فيها أن مسألة واحدة اسمها SAT لها خاصية غريبة: كل مسألة في NP يمكن تحويلها إليها في وقت متعدد الحدود. ومسألة SAT، واسمها الكامل مسألة قابلية الإرضاء Boolean Satisfiability، تسأل: لدينا صيغة منطقية فيها متغيرات كل منها صح أو خطأ، فهل توجد قيم للمتغيرات تجعل الصيغة كلها صحيحة؟ وبعد سنة نشر Richard Karp ورقة Reducibility among Combinatorial Problems وأثبت أن 21 مسألة مشهورة لها نفس الخاصية، منها تلوين الرسوم البيانية وحقيبة الظهر Knapsack والمسار الذي يمر بكل النقاط. وهذه المسائل تسمى NP-Complete، أي أنها أصعب مسائل NP: لو وجد أحد حلاً سريعاً لواحدة منها فقط، لصار عندنا حل سريع لكل مسائل NP، أي أن P = NP.
والتحويل Reduction هنا هو الفكرة الهندسية المهمة: أن تكتب مسألتك بلغة مسألة أخرى. فجدول المناوبات مثلاً يمكن كتابته كصيغة SAT، حيث المتغير «الموظف 7 يعمل في مناوبة الثلاثاء الليلية» صح أو خطأ، وكل قيد يصبح شرطاً منطقياً. وهذا ليس تمريناً نظرياً، فهناك برامج حل SAT Solvers يتنافس مطوروها كل سنة في مسابقة SAT، وتستخدمها أدوات تعرفها: مكتبة libsolv التي تحل اعتماديات الحزم في مديري حزم مثل zypper وdnf، ومدير الحزم في لغة Dart الذي يوثق خوارزمية الحل PubGrub الخاصة به، لأن اختيار إصدارات حزم متوافقة مع بعضها مسألة من نفس هذا النوع. وقد شرحنا مديري الحزم في مقال مديرو الحزم.
مختبر SAT: البحث الشامل Brute Force مقابل DPLL
لنرى الانفجار بأعيننا. كتبنا في sat.py مولداً لصيغ 3-SAT عشوائية، أي صيغ كل شرط فيها ثلاثة متغيرات، ثم طريقتين للحل. وثبتنا البذور العشوائية Seeds، فكل تشغيل يبني نفس الصيغ. وأهم ما في الملف:
def random_3sat(n, seed, ratio=4.26):
rnd = random.Random(seed)
return [tuple(v if rnd.random() < 0.5 else -v for v in rnd.sample(range(1, n + 1), 3)) for _ in range(round(n * ratio))]
def check(formula, assign): # assign[v] is True/False, index 1..n
return all(any(assign[abs(l)] == (l > 0) for l in c) for c in formula)
def brute_force(formula, n):
tried = 0
for bits in product((False, True), repeat=n):
tried += 1
a = (None,) + bits
if check(formula, a):
return a, tried
return None, triedفي الكود أعلاه لاحظ التالي:
- كل شرط Clause ثلاثة أرقام، والرقم السالب يعني نفي المتغير، فالشرط
(3, -7, 12)يعني «المتغير 3 صح، أو المتغير 7 خطأ، أو المتغير 12 صح». - عدد الشروط هو عدد المتغيرات مضروباً في 4.26، وسوف نشرح لماذا هذا الرقم بالذات بعد قليل.
- الدالة
checkهي التحقق، وهي تمر على الشروط مرة واحدة، أي أن وقتها يتناسب مع حجم الصيغة، وهذا ما يجعل SAT في NP. brute_forceتجرب كل التوزيعات الممكنة، وعددها2ⁿ.
والطريقة الثانية هي خوارزمية DPLL، التي تحمل أسماء Davis وPutnam وLogemann وLoveland، وهي أساس أغلب برامج حل SAT الحديثة. وفكرتها أن تختار متغيراً وتجرب له قيمة، ثم تبسط الصيغة، فإذا بقي شرط فيه متغير واحد فقيمته صارت إجبارية، وهذا ما يسمى نشر الوحدة Unit Propagation، وإذا وصلت إلى شرط فارغ فقد فشل هذا الفرع فترجع وتجرب القيمة الأخرى. والكود الكامل في الملف، وهو قرابة أربعين سطراً.
ولنأخذ مثالاً صغيراً لترى لماذا DPLL أسرع بكثير. لدينا ثلاثة شروط: (1 أو 2) و(ليس 1 أو 3) و(ليس 3). البحث الشامل يجرب ثمانية توزيعات للمتغيرات الثلاثة. أما DPLL فتبدأ بنشر الوحدة: الشرط الثالث فيه متغير واحد، فالمتغير 3 يجب أن يكون خطأ دون أي تجربة، وعندها يصبح الشرط الثاني (ليس 1) وحده، فالمتغير 1 خطأ إجبارياً، فيصبح الشرط الأول (2) وحده، فالمتغير 2 صح. وصلنا إلى الحل دون أن نخمن مرة واحدة. وفي الصيغ الحقيقية لا يكفي نشر الوحدة وحده، فتخمن الخوارزمية قيمة متغير، وتختار في نسختنا الحرف الأكثر تكراراً في الشروط المتبقية، ثم تنشر النتائج، فإذا وصلت إلى تناقض رجعت وجربت العكس. وكل تخمين صحيح يوفر نصف شجرة البحث، وكل نشر يقطع فروعاً كاملة دون تجربتها، ولهذا كان عدد الاستدعاءات في المختبر عشرات بدلاً من ملايين. ولكن في أسوأ حالة قد تضطر الخوارزمية إلى الرجوع في كل مستوى، فتعود شجرة البحث إلى حجمها الأسي.
وللمقارنة العادلة اخترنا لكل حجم صيغة ليس لها حل UNSAT، لأن البحث الشامل في هذه الحالة يجب أن يجرب كل الاحتمالات، فهي أسوأ حالة له. والمخرج كما يلي:
n clauses 2^n brute tried brute s dpll calls dpll s
12 51 4,096 4,096 0.04 11 0.001
14 60 16,384 16,384 0.19 19 0.001
16 68 65,536 65,536 0.43 13 0.001
18 77 262,144 262,144 1.57 11 0.001
20 85 1,048,576 1,048,576 9.45 37 0.003
22 94 4,194,304 4,194,304 30.89 19 0.002ولنقرأ الجدول:
- العمود
brute triedيساوي2^nتماماً في كل سطر، أي أن البحث الشامل جرب كل التوزيعات ليتأكد أنه لا يوجد حل. - كل متغيرين إضافيين يضربان العمل في 4، وكان يجب أن يضربا الوقت في 4 أيضاً، ولكن الوقت قفز من 1.57 إلى 9.45 ثانية بين 18 و20 متغيراً، أي ستة أضعاف. والسبب أن الجهاز كان يشغل أعمالاً أخرى في نفس الوقت، فلا تقرأ كل رقم وحده، وانظر إلى الاتجاه.
- عند 22 متغيراً فقط احتاج البحث الشامل 31 ثانية، ومع نفس الاتجاه سوف يحتاج 30 متغيراً قرابة ساعتين، و40 متغيراً قرابة 94 يوماً، و60 متغيراً قرابة 270 ألف سنة.
- DPLL حسمت نفس الصيغ في أجزاء من الميلي ثانية، بعشرات الاستدعاءات فقط بدلاً من الملايين.

فهل حلت DPLL المشكلة؟ لنعطها صيغاً أكبر، خمس صيغ لكل حجم، ونقيس الوسيط والأسوأ وزمن التحقق من الحل عندما يوجد:
n clauses SAT/5 dpll calls (median) dpll s (median) dpll s (max) check ms
50 213 3 75 0.020 0.065 0.166
75 320 4 151 0.059 0.401 0.368
100 426 3 343 0.156 2.729 0.409
125 532 4 7,457 6.944 19.117 0.414- العمود
SAT/5يقول كم صيغة من الخمس لها حل، وهو قرابة النصف في كل حجم. - الوسيط في عدد الاستدعاءات بقي صغيراً حتى 100 متغير، ثم قفز من 343 إلى 7,457 عند 125 متغيراً، وأسوأ صيغة أخذت 19 ثانية.
- والعمود الأخير هو قلب القصة: التحقق من الحل، عندما وجد، أخذ أقل من نصف ميلي ثانية في كل الأحجام. أي أن الحل نفسه أخذ حتى 19 ثانية، والتحقق منه أقل من ميلي ثانية، وهذا بالضبط الفرق بين «الإيجاد» و«التحقق» الذي يعرف NP.
وهنا المشكلة الحقيقية التي واجهناها: في أول محاولة أضفنا أحجام 150 و200 متغيراً، وتركنا التشغيل يعمل، وبعد أربع وعشرين دقيقة لم ينته، ولم يطبع حتى السطر الأول. والسبب الثاني كان بسيطاً: Python تجمع المخرج في ذاكرة مؤقتة Buffer عندما يذهب إلى ملف بدلاً من الشاشة، فلم نر حتى النتائج التي اكتملت، والحل هو الخيار python3 -u الذي يطبع كل سطر فوراً، وهو مكتوب الآن في run.sh. أما السبب الأول فهو موضوع هذا المقال: خوارزمية أذكى بكثير من البحث الشامل، ومع ذلك فإن 200 متغير عند هذه النسبة كانت أكثر مما تحتمله نسختنا البسيطة. والبرامج الحديثة لحل SAT تحل صيغاً فيها ملايين المتغيرات من مسائل حقيقية، لأنها تضيف تعلم الشروط من الفشل وإعادة التشغيل الذكية، ولكنها تبقى أسية في أسوأ حالة.
ماذا يحدث إذا غيرنا عدد الشروط؟ انتقال الطور Phase Transition
لماذا 4.26 شرطاً لكل متغير؟ لنجرب التغيير بأنفسنا: نثبت عدد المتغيرات عند 100، ونغير النسبة بين 2 و6، والمخرج كما يلي:
n=100
ratio clauses SAT/5 dpll calls (median) dpll s (median) dpll s (max)
2.0 200 5 51 0.005 0.007
3.0 300 5 41 0.007 0.007
4.26 426 3 343 0.244 3.622
5.0 500 0 2,011 1.951 3.764
6.0 600 0 499 0.541 1.289
- عند نسبة 2 و3 كانت كل الصيغ الخمس لها حل، وانتهت DPLL في أقل من 10 ميلي ثانية، لأن القيود قليلة وأي اختيار معقول ينجح.
- عند 4.26 صارت ثلاث صيغ فقط لها حل، وقفز الوقت.
- عند 5 لم يعد لأي صيغة حل، وكان الوقت في أعلاه، لأن الخوارزمية يجب أن تثبت أنه لا يوجد حل، والقيود ما زالت غير كافية لتظهر التناقض بسرعة.
- عند 6 نزل الوقت مرة أخرى، لأن القيود الكثيرة تتناقض بسرعة.
وهذا ما يسمى انتقال الطور Phase Transition في SAT: الصيغ الأصعب تقع في المنطقة التي ينتقل فيها احتمال وجود حل من «غالباً نعم» إلى «غالباً لا». ولهذا تصنف مجموعة SATLIB المعروفة صيغها العشوائية الصعبة على أنها من «منطقة انتقال الطور»، وأكبرها فيه 250 متغيراً و1,065 شرطاً، أي 4.26 لكل متغير. والدرس العملي أن صعوبة المسألة لا تعتمد على حجمها فقط، وإنما على شكلها، فجدول مناوبات بقيود قليلة أو قيود كثيرة متناقضة قد يحل في ثوان، وجدول على حافة الإمكان قد لا يحل أبداً.
مختبر البائع المتجول Travelling Salesman Problem
الآن نعود إلى مندوب التوصيل في أول المقال. مسألة البائع المتجول TSP تسأل: لدينا مدن والمسافات بينها، فما أقصر جولة تمر بكل مدينة مرة واحدة وترجع إلى البداية؟ وصيغتها كسؤال نعم أو لا، «هل توجد جولة أقصر من طول معين؟»، هي NP-Complete. وكتبنا في tsp.py ثلاث طرق، على نقاط عشوائية ثابتة البذرة في مربع طول ضلعه 100:
- البحث الشامل: نثبت المدينة الأولى ونجرب كل ترتيبات الباقي، وعددها
(n-1)!. - البرمجة الديناميكية Dynamic Programming بطريقة Held وKarp من 1962: نحفظ لكل مجموعة من المدن ولكل مدينة أخيرة أقصر مسار، فيصبح الوقت
n² · 2ⁿبدلاً منn!، وهو ما زال أسياً ولكنه أفضل بكثير. - حل تقريبي Heuristic: نبدأ بأقرب مدينة لم نزرها Nearest Neighbour، ثم نحسن الجولة بقلب أي جزء منها يقصرها، وهي طريقة 2-opt، حتى لا يبقى تحسين. وهذا لا يضمن الأفضل، ولكنه سريع جداً.
والمخرج للبحث الشامل كما يلي:
n=8 tours= 5,040 brute= 0.01 s best=280.85
n=9 tours= 40,320 brute= 0.11 s best=284.93
n=10 tours= 362,880 brute= 0.75 s best=305.93
n=11 tours= 3,628,800 brute= 17.39 s best=357.78
n=12 tours= 39,916,800 brute= 103.78 s best=279.79كل مدينة إضافية ضربت عدد الجولات في عددها، فمن 11 إلى 12 مدينة صار العدد 11 ضعفاً، وأخذت 12 مدينة 104 ثوان، أي قرابة 2.6 ميكروثانية لكل جولة. وبنفس السرعة سوف تحتاج 13 مدينة قرابة 21 دقيقة، و15 مدينة قرابة يومين ونصف، و20 مدينة قرابة عشرة آلاف سنة. ولاحظ أن الجولة الأفضل لاثنتي عشرة مدينة كانت أقصر من جولة عشر مدن، والسبب أن كل حجم له نقاط عشوائية مختلفة. ثم المخرج للبرمجة الديناميكية والحل التقريبي معاً:
n=10 held-karp= 0.01 s best=305.93 | heuristic= 0.3 ms len=305.93 gap= 0.00%
n=12 held-karp= 0.06 s best=279.79 | heuristic= 0.1 ms len=279.79 gap= 0.00%
n=14 held-karp= 0.26 s best=301.32 | heuristic= 0.1 ms len=302.59 gap= 0.42%
n=16 held-karp= 1.27 s best=326.56 | heuristic= 0.2 ms len=326.56 gap=-0.00%
n=18 held-karp= 7.54 s best=327.99 | heuristic= 0.2 ms len=327.99 gap= 0.00%- Held-Karp وجدت نفس الجولة الأفضل التي وجدها البحث الشامل لعشر واثنتي عشرة مدينة، في 0.06 ثانية بدلاً من 104 ثوان.
- ولكنها أيضاً تنفجر: كل مدينتين إضافيتين تضربان الوقت في خمسة تقريباً، فـ 18 مدينة أخذت 7.5 ثانية، وبنفس الاتجاه سوف تحتاج 30 مدينة قرابة يوم كامل، مع ذاكرة تحفظ ملايين المسارات الجزئية.
- الحل التقريبي أخذ أقل من ميلي ثانية، ووجد الجولة الأفضل نفسها في أربع حالات من خمس، وفي الحالة الخامسة كانت جولته أطول بـ 0.42% فقط. أما
-0.00%فهو فرق صغير جداً بين طريقتين لجمع نفس الأرقام العشرية، أي أن الجولتين متساويتان، وقد شرحنا سبب هذه الفروق في مقال الأرقام العشرية Floating Point من الداخل.
ثم أعطينا الحل التقريبي أحجاماً لا يمكن حلها بدقة بأي من الطريقتين:
n=100 heuristic= 0.01 s len=839.20
n=200 heuristic= 0.05 s len=1192.16
n=400 heuristic= 0.17 s len=1609.88
n=800 heuristic= 1.64 s len=2257.93
ثمانمئة مدينة في 1.6 ثانية. ونحن لا نعرف كم تبعد هذه الجولات عن الأفضل، لأننا لا نستطيع حساب الأفضل، ولكن ما رأيناه في الأحجام الصغيرة يعطينا ثقة معقولة. وهذا هو الطريق الذي تسلكه شركات التوصيل والطيران في الواقع: حلول تقريبية جيدة بسرعة، بدلاً من الحل الأفضل الذي لا يصل أبداً. وفي الجهة الأخرى، تبين مجموعة أبحاث TSP في جامعة Waterloo أن الحل الدقيق لمسائل كبيرة جداً ممكن بأدوات متخصصة، فقد حل فريق منهم مسألة pla85900 التي فيها 85,900 مدينة حلاً مثبتاً أنه الأفضل في 2005 و2006 باستخدام برنامج Concorde. وهذا لا يناقض ما سبق، فالمسألة صعبة في أسوأ حالة، أما المسائل الحقيقية فلها بنية تستغلها الأدوات الذكية.
لماذا يهمك سؤال P مقابل NP؟
لو أثبت أحد يوماً أن P = NP بطريقة عملية، فسوف يتغير الكثير: جدولة المصانع، والتوزيع، وتصميم الدوائر الإلكترونية، والبحث عن البراهين الرياضية. ولكن أيضاً جزء كبير من التشفير Encryption الذي نعتمد عليه، لأن التشفير يعتمد على مسائل يسهل التحقق من حلها ويصعب إيجاده، مثل إيجاد عوامل رقم كبير، التي شرحناها في مقال الرياضيات خلف RSA. ولاحظ الدقة هنا: تحليل الرقم إلى عوامل مسألة في NP، ولكن لم يثبت أحد أنها NP-Complete، فقد تكون أسهل من SAT دون أن نعرف، وأمان RSA يعتمد على صعوبتها هي تحديداً، لا على سؤال P مقابل NP وحده.
وأغلب الباحثين يعتقدون أن P ≠ NP، أي أن هناك مسائل يسهل التحقق منها ويستحيل حلها بسرعة، ولكن هذا اعتقاد وليس برهاناً. وبالنسبة لك كمهندس، فالنتيجة العملية واحدة في الحالتين حتى يحل السؤال: عندما تعرف أن مسألتك NP-Complete فلا تبحث عن خوارزمية سريعة دقيقة لكل الحالات، فقد بحث عنها آلاف الأشخاص قبلك خمسين سنة، وإنما اختر من الطرق العملية في القسم التالي.
ماذا تفعل عملياً؟ جدول القرار Decision Table
| حالتك | الطريقة | مثال من المختبر |
|---|---|---|
| الحجم صغير جداً ومضمون أن يبقى صغيراً | البحث الشامل، فهو أبسط وأصح | حتى 10 مدن في أقل من ثانية |
| الحجم متوسط وتحتاج الأفضل | برمجة ديناميكية أو تفرع وتقليم Branch and Bound | Held-Karp حتى 18 مدينة في 7.5 ثانية |
| قيود كثيرة من نوع نعم أو لا | حولها إلى SAT أو برمجة خطية بأعداد صحيحة واستخدم برنامج حل جاهزاً | DPLL البسيطة حسمت 100 متغير في أقل من أربع ثوان |
| الحجم كبير ويكفيك حل جيد | حل تقريبي Heuristic مع تحسين محلي | 800 مدينة في 1.6 ثانية |
| لا تعرف هل البرنامج سوف ينتهي | مهلة Timeout وميزانية خطوات، واقبل الإجابة «لا أعرف» | الدالة simulate |
| تحتاج أداة تحليل للكود | اقبل أنها سوف تخطئ في جهة، واختر الجهة الأقل ضرراً | مبرهنة Rice |
أخطاء شائعة Common Mistakes
- اختبار الخوارزمية الأسية على مدخل صغير ثم نشرها: عشر مدن في ثانية لا تعني عشرين مدينة في ثانيتين، وإنما في عشرة آلاف سنة.
- البحث عن حل دقيق وسريع لمسألة NP-Complete قبل أن تعرف أنها كذلك: ابحث أولاً هل مسألتك معروفة، فقد تجد اسمها في قائمة Karp أو في كتب الخوارزميات.
- كتابة برنامج حل خاص بدلاً من استخدام برنامج حل جاهز: نسختنا من DPLL أربعون سطراً وتوقفت عند 200 متغير، والبرامج المتخصصة سنوات من العمل.
- الحكم على صعوبة المسألة من حجمها وحده: رأيت أن 100 متغير عند نسبة 3 حلت في 7 ميلي ثانية، وعند نسبة 5 في ثانيتين.
- انتظار أداة تحليل لا تخطئ: مبرهنة Rice تقول إنها غير موجودة، فاقرأ التحذيرات بعقل.
- تشغيل التجارب الطويلة دون مخرج فوري:
python3 -uأو تفريغ المخرج دورياً، حتى ترى النتائج التي اكتملت قبل أن توقف التشغيل. - غياب المهلة في أي عملية قد لا تنتهي: من استدعاء الشبكة إلى حلقة البحث في برنامجك.
قائمة تحقق Checklist عندما تواجه مسألة بحث
- ما حجم المدخل اليوم، وما حجمه بعد سنة؟
- هل الحل البسيط أسي؟ احسب وقته عند الحجم القادم قبل أن تكتبه.
- هل مسألتك معروفة باسم مثل SAT أو TSP أو Knapsack أو تلوين الرسوم؟
- هل تحتاج الحل الأفضل فعلاً، أم يكفيك حل جيد مع حد معروف للفرق؟
- هل يوجد برنامج حل جاهز، مثل SAT Solver أو برنامج برمجة خطية، يمكنك تحويل مسألتك إليه؟
- هل وضعت مهلة وميزانية لكل بحث، وهل تعرف ماذا يفعل النظام عندما تنتهي؟
- هل يمكنك التحقق من الحل الناتج بسرعة قبل أن تستخدمه؟
حذف المختبر Cleanup
كل التجارب عملت في Containers مؤقتة بالخيار --rm، فيكفي حذف الـ Image:
docker rmi scp6-cpxالخلاصة
- مشكلة التوقف غير قابلة للحسم: لا يوجد برنامج يقرر لكل برنامج هل سوف يتوقف، والبرهان بالقطر يبني لكل محاولة برنامجاً يعاكسها، كما رأيت مع الدوال الأربع في المختبر.
- مبرهنة Rice توسع النتيجة إلى كل خاصية سلوكية للبرامج، ولهذا تخطئ أدوات التحليل دائماً في جهة ما، ولهذا نستخدم المهلة.
- الصنف P مسائل يمكن حلها بسرعة، والصنف NP مسائل يمكن التحقق من حلها بسرعة، والمسائل NP-Complete هي أصعبها، وسؤال P = NP مفتوح.
- في المختبر احتاج البحث الشامل في SAT إلى 31 ثانية لاثنين وعشرين متغيراً، وDPLL أخرت الانفجار إلى قرابة 125 متغيراً، والتحقق من الحل بقي أقل من نصف ميلي ثانية.
- أصعب صيغ SAT العشوائية في منطقة انتقال الطور، حيث يتغير الجواب من نعم إلى لا.
- في البائع المتجول توقف البحث الشامل عند 12 مدينة وHeld-Karp عند 18، بينما وجد الحل التقريبي جولات بفرق أقصاه 0.42% عن الأفضل، ووصل إلى 800 مدينة في 1.6 ثانية.
ولتكمل هذه المرحلة اقرأ ابن مفسراً صغيراً بيدك لترى كيف يقرأ برنامج برنامجاً آخر، والخوارزميات وتعقيد Big-O إذا أردت مراجعة النمو والتعقيد، والرياضيات خلف RSA لترى كيف يبنى الأمان على مسائل صعبة، وفضاء النواة واستدعاءات النظام والعمليات وجدولة المعالج من نفس المرحلة.
سجل التحديثات
- أكتوبر 2026: كتابة المقال وتشغيل كل التجارب على Python 3.13.5 في Container من debian:trixie-slim بمعالج واحد.