هل دحض نموذج من OpenAI فرضية الزمن الأسي؟

في 26 أكتوبر نشرت OpenAI في مستودع openai/math ورقة بعنوان “The Exponential Time Hypothesis is False”. وبحسب الورقة، فإن نموذجًا داخليًا غير معلن من OpenAI دحض فرضية الزمن الأسي (ETH)، وهي إحدى الافتراضات الأساسية في نظرية التعقيد الحسابي. وتفحص الورقةَ مع صياغتها الرسمية في Lean مجموعةٌ مستقلة من علماء الحاسوب، بينهم اثنان من واضعي الفرضية نفسها.

ما هي فرضية الزمن الأسي؟

تفترض ETH (Exponential Time Hypothesis) أن مسألة 3-SAT، أي التحقق مما إذا كان يمكن إرضاء صيغة منطقية جُملها من ثلاثة متغيرات، لا يمكن حسمها بأسرع من زمن 2^Ω(n) لعدد n من المتغيرات. وبعبارة أبسط: مع كل متغير إضافي ينمو الزمن نموًا أسيًا، ولن تغيّر ذلك أي خوارزمية ذكية.

صاغ الفرضية راسل إمباليازو وراماموهان باتوري (مع فرانسيس زين). وتستند إلى ETH مئات الأبحاث التي تثبت أن مسألة ما في المخططات البيانية أو قواعد البيانات أو البيولوجيا الحسابية “لا يمكن” حلها بشكل أسرع (كما يذكّر موقع The Next Web).

ما الذي أثبته نموذج OpenAI بالضبط؟

تقدم الورقة خوارزمية حتمية تعدّ بدقة جميع التعيينات التي ترضي صيغة k-CNF لكل قيمة ثابتة k ≥ 2. وهي تعمل بذاكرة متعددة الحدود وفي زمن (n + m)^O(1) · 2^(n/(log n)^(1/2+o(1)))، أي زمن دون أسي. وتكفي حالة 3-SAT لدحض ETH.

اللافت أن الخوارزمية لا تجيب بـ“نعم” أو “لا” فقط، بل تعدّ الحلول. ومن ذلك تستخلص الورقة نتائج أخرى:

1. خوارزميات دون أسية لعدّ تلوينات المخططات والمجموعات المستقلة والتوافقات التامة،
2. تقريبات بأي دقة مطلوبة لمسألة Max-k-SAT في زمن دون أسي،
3. حدًا أدنى جديدًا لحجم الدارات المنطقية للصنف E^NP.

وبحسب The Next Web، وجد النموذج البرهان في 16 أكتوبر، وبعد يوم واحد كان قد تحقق منه في Lean (لغة رسمية يتحقق بها الحاسوب من البراهين). وفي سجل تغييرات المستودع تذكر OpenAI أن الورقة نُشرت مع صياغتها الرسمية في Lean.

من يتحقق من البرهان؟

يقود المجموعة التي ستفحص البرهان وتشرحه راسل إمباليازو وراماموهان باتوري (UC San Diego) وراين ويليامز (MIT). وبحسب سجل تغييرات المستودع، فقد نُشرت المواد فورًا بطلب من هذه المجموعة تحديدًا، كي يتمكن الجميع من التحقق منها. وكتب ويليامز على X أن نموذجًا داخليًا من OpenAI أنتج “claimed refutation of ETH”، أي دحضًا مُعلنًا لـETH.

لم يوقّع الباحثون أي اتفاقيات عدم إفصاح ولا يتقاضون أجرًا على ذلك (بحسب The Next Web). وطلبوا من OpenAI نشر جميع البيانات الخام وتمويل مؤتمر حول تبعات النتيجة، فوافقت الشركة. لكنهم يؤكدون في رسالة مفتوحة أن مشاركتهم ليست تأكيدًا للنتيجة (“should not be taken as certification of the claim”)، مضيفين أنه إذا كان البرهان صحيحًا فإن “it will change an important part of theoretical computer science”.

هل هذا جديد في عالم الذكاء الاصطناعي؟

ليست هذه أول منشورات OpenAI من هذا النوع. فكما نعلم، رفعت الشركة في 6 أكتوبر إلى المستودع نفسه أكثر من 700 ورقة رياضية ولّدها النموذج. ونقرأ في ملف README للمستودع أن النموذج تلقى نحو 4000 مسألة مفتوحة، وأن كل نتيجة استغرقت في المتوسط ثلاث ساعات من “التفكير” بمستوى ChatGPT Pro.

الجديد أن OpenAI أعلنت في 26 أكتوبر ثلاث نتائج دفعة واحدة، واختارت لكل منها طريقًا مختلفًا (كما يصف موقع Unite.AI):

1. ETH: الورقة والبرهان في Lean متاحان للعموم، وتتحقق منهما مجموعة مفتوحة يقودها إمباليازو وباتوري وويليامز.
2. حدسية سوغ حول “local smoothing” في جميع الأبعاد، والتي تنتج عنها بحسب OpenAI حدسية كاكيا وحدسية التقييد لشتاين: نُشرت هي الأخرى مع برهان في Lean.
3. وجود نظرية يانغ-ميلز والديناميكا اللونية الكمومية (QCD) في أربعة أبعاد (إحدى مسائل الألفية لمعهد كلاي): لا توجد مواد حتى الآن. وقررت مجموعة يقودها الحائز على نوبل ديفيد غروس أن تصف النتيجة بنفسها.

وتعلن OpenAI أيضًا أنها لا تريد الفضل العلمي في اكتشافات نماذجها، بل يُفترض أن يذهب التقدير إلى الأشخاص الذين سيفهمونها ويصفونها. كما تبرعت الشركة بـ5 ملايين دولار لمؤسسة سايمونز لتمويل ورش عمل ومؤتمرات حول النتائج التي يولّدها الذكاء الاصطناعي.

ما الذي ينبغي الانتباه إليه؟

أولًا، حالة التحقق. فالصياغة الرسمية في Lean إشارة قوية، لكن يجب دائمًا التحقق من أن المبرهنة المكتوبة في Lean تقول فعلًا ما يقوله نص الورقة. وOpenAI نفسها تكتب في README أن بعض النتائج غير المصاغة رسميًا قد تحتوي أخطاء، وقد سحبت في 7 أكتوبر ثلاث أوراق بسبب خطأ في الإشارة في أحد البراهين. لذا لنتعامل مع النتيجة بحذر إلى أن تنهي المجموعة عملها.

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

ثالثًا، الوتيرة. فالنتيجة التي عمل عليها المنظّرون أكثر من 20 عامًا يُقال إن النموذج وجدها في إطار تقييم داخلي. وإذا تأكدت، فستكون على الأرجح أقوى مثال حتى الآن على أن الذكاء الاصطناعي يحقق اكتشافات مستقلة في علوم الحاسوب النظرية. وبالمناسبة يعود موضوع البراهين الرسمية الذي كتبت عنه في التحقق الرسمي مع Claude.

الأسئلة الشائعة

ما هي فرضية الزمن الأسي؟

هي افتراض في نظرية التعقيد بأن مسألة 3-SAT لا يمكن حلها في زمن أقل من 2^Ω(n) لعدد n من المتغيرات. صاغها إمباليازو وباتوري مع فرانسيس زين.

هل حلّت OpenAI مسألة P مقابل NP؟

لا. الخوارزمية دون أسية لكنها ليست متعددة الحدود، ويشير المؤلفون إلى أن النتيجة لا تنطبق على جميع مسائل NP.

هل تأكد دحض ETH بالفعل؟

ليس بعد. توجد صياغة رسمية في Lean، لكن المجموعة المستقلة بقيادة إمباليازو وباتوري وويليامز ما زالت تفحصها، وتؤكد أن مشاركتها لا تعني التأكيد.

أي نموذج من OpenAI فعل ذلك؟

نموذج داخلي غير معلن. ولا تذكر OpenAI اسمه في ملف README للمستودع.