دليل طبيعي

في نظرية التعقيد الحسابي ، يُعدّ البرهان الطبيعي نوعًا من البراهين التي تُثبت اختلاف فئة تعقيد عن أخرى. ورغم أن هذه البراهين "طبيعية" إلى حد ما، إلا أنه يمكن إثبات (بافتراض صحة فرضية شائعة حول وجود الدوال شبه العشوائية ) أنه لا يمكن استخدام أي برهان من هذا القبيل لحل مشكلة P مقابل NP .

تم تقديم مفهوم البراهين الطبيعية من قبل ألكسندر رازبوروف وستيفن روديتش في مقالتهما "البراهين الطبيعية"، التي عُرضت لأول مرة في عام 1994، ونُشرت لاحقًا في عام 1997، والتي حصلوا عليها على جائزة غودل لعام 2007. ^{[ 1 ]}

على وجه التحديد، تُثبت البراهين الطبيعية حدودًا دنيا لتعقيد الدوائر للدوال المنطقية . يُظهر البرهان الطبيعي، بشكل مباشر أو غير مباشر، أن للدالة المنطقية خاصية توافقية طبيعية معينة . بافتراض وجود دوال شبه عشوائية ذات "صعوبة أسية" كما هو محدد في نظريتهما الرئيسية، يُبين رازبوروف وروديتش أن هذه البراهين لا تستطيع التمييز بين فئات تعقيد معينة. والجدير بالذكر أنه بافتراض وجود دوال شبه عشوائية، فإن هذه البراهين لا تستطيع التمييز بين فئتي التعقيد P وNP. ^{[ 2 ]}

فعلى سبيل المثال، تنص مقالتهم على ما يلي:

[...] لنفترض استراتيجية إثبات شائعة لإثبات أن P ≠ NP:

• صِغْ مفهومًا رياضيًا لـ "الاختلاف" أو "التشتت" أو "التباين" في قيم دالة منطقية، أو في متعدد السطوح المرتبط بها أو في بنية أخرى. [...]
• أثبت باستخدام الاستدلال الاستقرائي أن الدوائر ذات الحجم متعدد الحدود لا يمكنها حساب سوى الدوال ذات التباين "المنخفض". [...]
• ثم أظهر أن SAT ، أو أي دالة أخرى في NP، لديها تباين "عالي".

تُقدّم نظريتنا الرئيسية في القسم 4 دليلاً على أنه لا يمكن لأي استراتيجية إثبات على هذا النحو أن تنجح أبداً. ^{[ 3 ]}

تُعرَّف خاصية الدوال المنطقية بأنها طبيعية إذا احتوت على خاصية تُحقق شرطي البنائية والكبر اللذين حددهما رازبوروف وروديتش. باختصار، يتطلب شرط البنائية أن تكون الخاصية قابلة للتقرير في زمن (شبه) متعدد الحدود عند إعطاء جدول الحقيقة ذي الحجم 2 ^{^n} لدالة منطقية ذات n مدخلات كمدخلات، وذلك تقاربًا مع ازدياد n . وهذا يُعادل زمنًا أُسّيًا أحاديًا بالنسبة لـ n . ومن المرجح أن تُحقق الخصائص سهلة الفهم هذا الشرط. أما شرط الكبر فيتطلب أن تكون الخاصية صحيحة لجزء كبير بما فيه الكفاية من مجموعة جميع الدوال المنطقية.

تُعدّ خاصية ما مفيدة ضد فئة التعقيد C إذا كان كل تسلسل من الدوال المنطقية التي تحمل هذه الخاصية يُعرّف لغةً خارج فئة C بشكل متكرر لا نهائي . والبرهان الطبيعي هو برهان يُثبت أن لغةً معينة تقع خارج فئة C ويستند إلى خاصية طبيعية مفيدة ضد هذه الفئة .

يقدم رازبوروف وروديتش عددًا من الأمثلة على براهين الحد الأدنى ضد الفئات C الأصغر من P/poly ، والتي يمكن "تطبيعها"، أي تحويلها إلى براهين طبيعية. يتناول أحد الأمثلة المهمة براهين تثبت أن مسألة التكافؤ ليست ضمن الفئة AC ^0. ويقدمان أدلة قوية على أن التقنيات المستخدمة في هذه البراهين لا يمكن توسيعها لإظهار حدود دنيا أقوى. على وجه الخصوص، لا يمكن أن تكون البراهين الطبيعية لـ AC ⁰ مفيدة ضد AC ⁰ [m] .

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

هناك اعتقاد سائد حاليًا بأن آلية هذه الورقة البحثية تعيق في الواقع إثباتات الحد الأدنى لفئة التعقيد TC ⁰ للدوائر العتبية ذات العمق الثابت والحجم متعدد الحدود، والتي يُعتقد أنها أصغر من P/poly، ولكن لم يُثبت ذلك بعد. ^{[ 4 ]} ويعود هذا الاعتقاد إلى أنه، وفقًا لتخمينات شائعة حول صعوبة التحليل في مجموعات منحنيات إهليلجية معينة ، توجد دوال شبه عشوائية صعبة أُسّيًا قابلة للحساب في TC ^{0. [ 5 ]} ومع ذلك ، يعتقد بعض الباحثين أن قيود رازبوروف-روديتش تُعدّ في الواقع دليلًا جيدًا لما قد ينطوي عليه إثبات الحد الأدنى "الخارق للطبيعة"، مثل الخصائص الصعبة أو الكاملة للفضاء الأُسّي. ^{[ 6 ]}

• أ. أ. رازبوروف (2004). "البراهين والحسابات الممكنة: الشراكة والاندماج". وقائع المؤتمر الدولي الحادي والثلاثين لـ ICALP . سلسلة محاضرات في علوم الحاسوب. المجلد  3142. الصفحات 8-14 . ( مسودة )
• لانس فورتناو (2006-05-10). "أهمية البراهين الطبيعية" .
• تشاو، تيموثي واي. (2011)، "ما هو... البرهان الطبيعي؟" (ملف PDF) ، إشعارات الجمعية الأمريكية للرياضيات ، 58 (11)، الجمعية الأمريكية للرياضيات ، تاريخ الاسترجاع 2014-08-05