تخيل أنك تحاول العثด على صديق محدد في مدينة ضخمة وفوضوية. لديك خريطة (قاعدة البيانات) توضح أماكن الناس الآن، ولكن لديك أيضًا كتاب قواعد (الأنطولوجيا - Ontology) يخبرك بأشياء لا تظهرها الخريطة بشكل مباشر. على سبيل المثال، قد يقول كتاب القواعد: "إذا كانت أليس صديقة لبوب، فإن بوب صديق لأليس"، أو "إذا كنت تتابع شخصًا ما، فأنت متصل به". في عالم علوم الحاسوب، يُطلق على هذا اسم الإجابة على الاستعلامات المعتمدة على الأنطولوجيا (Ontology-mediated query answering). الأمر يشبه امتلاك دليل ذكي للغاية لا ينظر فقط إلى البيانات الخام، بل يستخدم المنطق لملء الفجوات، مما يعطيك صورة أكثر اكتمالاً للعالم.

ومع ذلك، تصبح عملية طرح الأسئلة معقدة عندما تبدأ في السؤال عن المسارات. فبدلاً من مجرد السؤال: "هل أليس صديقة لبوب؟"، قد تسأل: "هل يمكنني الوصول من أليس إلى بوب عبر سلسلة من الأصدقاء، حتى لو كانت هذه السلسلة طويلة جدًا وتدور حول نفسها؟". تُسمى هذه استعلامات المسار (Path queries). وهي ضرورية للتنقل في الشبكات المعقدة مثل وسائل التواصل الاجتماعي أو الويب الدلالي (Semantic Web). ولكن هنا تكمن المشكلة، فعندما تجمع بين أسئلة البحث عن المسارات وكتاب قواعد قوي، يصبح عمل الكمبيوتر صعبًا للغاية، بل وقد يكون مستحيلاً في وقت معقول. السؤال الكبير الذي صارع العلماء لحله هو: ما مدى صعوبة الإجابة على أسئلة المسار هذه حقًا عند امتلاك أنواع مختلفة من كتب القواعد؟

هذا البحث يشبه مجموعة من المحققين (جان فرانسوا باجيت، ميغين بيينفينو، ماري لور موغنير، وميشائيل تومازو) الذين قرروا رسم خريطة لصعوبة استعلامات المسار لنوعين شائعين جدًا من كتب القواعد: القواعد الخطية (Linear Rules) والقواعد المحروسة (Guarded Rules). فكر في "القواعد الخطية" كتعليمات بسيطة من خطوة واحدة (مثل "إذا كان أ صحيحًا، فإن ب صحيح")، و"القواعد المحروسة" كتعليمات أكثر تعقيدًا تتطلب وجود حقيقة "حارس" معينة قبل أن يتم تفعيلها (مثل "إذا كان أ صحيحًا وَ ب صحيحًا، فإن ج صحيح"). لم يكتفِ المؤلفون بالتخمين؛ بل أثبتوا بدقة مقدار القدرة الحوسبية المطلوبة لحل هذه الألغاز، مما خلق "مخطط صعوبة" دقيقًا لعلماء الحاسوب.

عمل المحققين: رسم خريطة الصعوبة

تعامل المؤلفون مع هذه المشكلة من خلال معاملة عملية الاستدلال في الكمبيوتر كلعبة "مطاردة". تخيل لعبة تبدأ فيها ببضع حقائق معروفة وتستمر في تطبيق القواعد لتوليد حقائق جديدة حتى لا تعود قادراً على فعل المزيد. يُسمى هذا المطاردة (The Chase). التحدي في استعلامات المسار هو أن "المطاردة" قد تستمر للأبد، مما يخلق شبكة لا نهائية من الاتصالات. أراد الباحثون معرفة: هل يمكننا إيقاف اللعبة مبكرًا ومع ذلك نعرف الإجابة؟ وكم من الوقت يستغرق التحقق مما إذا كان المسار موجودًا؟

لقد قسموا تحقيقهم إلى سيناريوهين رئيسيين: تعقيد البيانات (Data Complexity) (ما مدى الصعوبة عندما يكون كتاب القواعد صغيرًا وثابتًا، ولكن المدينة ضخمة؟) والتعقيد المشترك (Combined Complexity) (ما مدى الصعوبة عندما يكون كل من كتاب القواعد والمدينة ضخمين؟).

القواعد البسيطة: القواعد الخطية

أولاً، نظروا إلى القواعد الخطية. وهي القواعد "البسيطة" حيث يكون متن القاعدة عبارة عن حقيقة واحدة فقط.

• الاكتشاف: وجدوا أنه إذا كنت تبحث فقط عن مجموعة بيانات محددة (تعقيد البيانات)، فإن الإجابة على أسئلة المسار هذه سهلة بشكل مفاجئ. إنها سهلة مثل التنقل في متاهة بسيطة على الهاتف؛ حيث يمكن للكمبيوتر القيام بذلك في زمن NL-complete. هذه هي نفس سرعة الإجابة على أسئلة المسار على خريطة عادية بدون أي كتاب قواعد!
• العقبة: إذا بدأت في تغيير القواعد نفسها (التعقيد المشترك)، تصبح الأمور أصعب. إذا كانت القواعد بسيطة وقصيرة، فلا يزال الأمر قابلاً للإدارة (PTime). ولكن إذا أصبحت القواعد طويلة ومعقدة بشكل تعسفي، تقفز الصعوبة إلى ExpTime-complete. وهذا يعني أن الوقت اللازم لحل المشكلة ينمو بشكل أسي، مثل كرة ثلج تتدحرج من فوق تلة، لكنها لا تزال قابلة للحل.

القواعد المعقدة: القواعد المحروسة

بعد ذلك، واجهوا القواعد المحروسة. وهي قواعد أكثر قوة ومرونة، وتسمح بعلاقات أكثر تعقيدًا، لكنها تأتي مع "حارس" يجب استيفاؤه.

• الاكتشاف: هنا، استخدم المؤلفون خدعة ذكية. لقد أظهروا أنه يمكنك ترجمة هذه القواعد "المحروسة" المعقدة إلى القواعد "الخطية" الأبسط، ولكن مع لمسة: الترجمة تجعل مجموعة القواعد تنفجر في الحجم.
• النتيجة: بسبب هذا الانفجار، تصبح الإجابة على استعلامات المسار تحت القواعد المحروسة أصعب بكثير. في الحالة العامة (عدد غير محدود من العناصر/Arity)، ترتفع الصعوبة إلى 2ExpTime-complete. هذا قفزة أسية مزدوجة، مما يعني أن الوقت المطلوب للحل ينمو بسرعة تفوق الخيال للمدخلات الكبيرة. ومع ذلك، إذا قمت بتحديد حجم القواعد (عدد محدود من العناصر/Bounded Arity)، فإن الصعوبة تنخفض إلى ExpTime-complete، وهو نفس مستوى صعوبة الإجابة على الأسئلة القياسية (وليس مجرد أسئلة المسار) تحت هذه القواعد.

"الحلقة" و"مخطط الإثبات"

كيف أثبتوا كل هذا؟ لقد اخترعوا أدوات ذهنية رائعة.

بالنسبة لـ القواعد الخطية، أدركوا أنه على الرغم من أن "المطاردة" تخلق شبكة لا نهائية، فإن أي مسار يتيه في "المجهول" (الجزء المجهول من المطاردة) ويعود إلى حقيقة معروفة يجب أن يكون قد بدأ وانتهى ضمن "ظل" حقيقة أصلية واحدة. أطلقوا على هذه المسارات اسم "الحلقات" (Loops). ومن خلال الحساب المسبق لجميع الحلقات الممكنة لكل نوع من الحقائق، استطاعوا بناء "ورقة غش" (جدول) تسمح للكمبيوتر بتخمين المسار دون الحاجة إلى محاكاة المطاردة اللانهائية. وهذا هو سبب انخفاض تعقيد البيانات؛ فالكمبيوتر ببساال يبحث عن الحلقة في ورقة الغش.

أما بالنسبة لـ CRPQs (وهي استعلامات مسار أكثر تعقيدًا يمكنها السؤال عن مسارات متعددة في آن واحد)، فقد استخدموا مفهومًا يسمى "مخططات الإثبات" (Proof Schemes). تخيل مخطط الإثبات كمخطط هندسي صغير ومحدود للمطاردة اللانهائية. بدلاً من بناء المدينة اللانهائية بأكملها، يبني الكمبيوتر نموذجًا صغيرًا وممثلًا يثبت وجود المسار. لقد أظهروا أنه إذا وجد مسار، فهناك دائمًا "مخطط" صغير يثبت ذلك. سمح لهم هذا بإثبات أنه على الرغم من صعوبة المشكلة، إلا أنها ليست مستحيلة—فهي فقط تتطلب الكثير من الذاكرة والوقت.

ما لم يجدوه (ولما-ذا يهم ذلك)

الورقة البحثية حذرة للغاية بشأن ما لا تدعيه. فهي لا تقول إن استعلامات المسار سهلة لجميع أنواع كتب القواعد. في الواقع، هي تسلط الضوء على أنه بالنسبة لأنواع أخرى من القواعد (مثل القواعد "اللاصقة" أو تلك التي تسمح بإعادة الكتابة)، فقد تكون المشكلة غير قابلة للحل (Undecidable) أو على الأقل أصعب بكثير دون حد علوي واضح. يشير المؤلفون صراحة إلى أنه بينما حلوا لغز التعقيد للقواعد الخطية والمحروسة، فإن المشهد لأنواع القواعد الأخرى لا يزال غامضًا.

كما يوضحون أنه بينما نتائجهم مثبتة رياضيًا، فإن الخوارزميات للحالات الأكثر صعوبة (مثل حالات 2ExpTime) بطيئة جدًا حاليًا بحيث لا يمكن استخدامها في الواقع العملي. إنها خرائط نظرية، وليست سيارات جاهزة للقيادة. ومع ذلك، بالنسبة للقواعد الخطية الأبسط، يقترحون أنه يمكن تحويل طريقة "الحلقة" الخاصة بهم إلى أداة عملية وسريعة، خاصة إذا تمت معالجة البيانات مسبقًا لملء الفجوات قبل أن يسأل المستخدم السؤال.

الصورة الكبيرة

في النهاية، يوفر هذا البحث أول "خريطة صعوبة" كاملة للتنقل في استعلامات المسار تحت نوعين رئيسيين من القواعد المنطقية. يخبرنا هذا أن:

1. القواعد البسيطة (الخطية) ممتازة للمهام الكثيفة البيانات لأنها سريعة الاستعلام، حتى مع المسارات المعقدة.
2. القواعد القوية (المحروسة) مرنة ولكنها تأتي بتكلفة حوسبية باهظة، خاصة عندما تصبح القواعد طويلة.
3. استعلامات المسار هي بطبيعتها أصعب من الأسئلة القياسية، لكننا نعلم الآن بالضبط مدى صعوبتها.

هذا العمل هو خطوة تأسيسية. فهو لا يكتفي بالقول "إنها صعبة"؛ بل يعطينا الحدود الرياضية الدقيقة لهذه الصعوبة. بالنسبة لعلماء الحاسوب الذين يبنون الجيل القادم من الرسوم البيانية للمعرفة (Knowledge Graphs) وأنظمة الذكاء الاصطناعي، فإن هذا هو الفرق بين التخمين بمدى قوة الخادم التي تحتاجها وبين معرفة بالضبط ما تحتاج لشرائه. إنه يحول رحلة ضبابية وغير مؤكدة إلى مسار مضاء جيدًا، يوضح لنا بالضبط أين توجد المنحدرات الشديدة وأين توجد الطرق الممهدة.