اختزال جدول الحقيقة

في نظرية الحوسبة ، يُعد اختزال جدول الحقيقة نوعًا من أنواع الاختزال من مشكلة القرار.${\displaystyle A}$مشكلة اتخاذ القرار${\displaystyle B}$لحل مشكلة في${\displaystyle A}$، يصف الاختزال الإجابة على${\displaystyle A}$كصيغة منطقية أو جدول حقيقة لعدد محدود من الاستعلامات إلى${\displaystyle B}$.

تُعدّ اختزالات جداول الحقيقة مرتبطة باختزالات تورينج ، وهي أضعف منها بشكلٍ قاطع. (أي أنه لا يمكن إجراء كل اختزال تورينج بين المجموعات باستخدام اختزال جداول الحقيقة، ولكن يمكن إجراء كل اختزال جداول الحقيقة باستخدام اختزال تورينج). يحسب اختزال تورينج من المجموعة B إلى المجموعة A انتماء عنصر واحد إلى B من خلال طرح أسئلة حول انتماء عناصر مختلفة إلى A أثناء الحساب؛ وقد يحدد الأسئلة التي يطرحها بشكلٍ تكيفي بناءً على إجابات الأسئلة السابقة. في المقابل، يجب على اختزال جداول الحقيقة أو اختزال جداول الحقيقة الضعيف تقديم جميع استعلاماته (المحدودة العدد) في الوقت نفسه. في اختزال جداول الحقيقة، يُعطي الاختزال أيضًا صيغة منطقية (جدول حقيقة) تُنتج، عند إعطائها إجابات الاستعلامات، الإجابة النهائية للاختزال.

تظهر اختزالات جداول الحقيقة في ورقة بحثية لإميل بوست نُشرت عام 1944. ^{[ 1 ]}

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

بما أن كل اختزال لجدول الحقيقة هو اختزال تورينج، فإذا كانت A قابلة للاختزال لجدول الحقيقة إلى B ( A ≤ _tt B )، فإن A قابلة للاختزال لتورينج إلى B ( A ≤ _TT B ). مع الأخذ في الاعتبار أيضًا قابلية الاختزال أحاديًا، وقابلية الاختزال متعددًا، وقابلية الاختزال الضعيف لجدول الحقيقة،

${\displaystyle A\leq _{1}B\Rightarrow A\leq _{m}B\Rightarrow A\leq _{tt}B\Rightarrow A\leq _{wtt}B\Rightarrow A\leq _{T}B}$،

أو بعبارة أخرى، فإن قابلية الاختزال من واحد إلى واحد تعني قابلية الاختزال من متعدد إلى واحد، مما يعني قابلية الاختزال في جدول الحقيقة، والتي بدورها تعني قابلية الاختزال الضعيفة في جدول الحقيقة، والتي بدورها تعني قابلية الاختزال تورينج.

علاوة على ذلك، فإن A قابلة للاختزال إلى B باستخدام جدول الحقيقة إذا وفقط إذا كانت A قابلة للاختزال إلى B باستخدام تورينج عبر دالة كلية على${\displaystyle 2^{\omega }}$الاتجاه الأمامي بديهي. أما بالنسبة للاتجاه العكسي، فلنفترض${\displaystyle \Gamma }$هي دالة قابلة للحساب كليًا. لبناء جدول الحقيقة لحساب A ( n )، ابحث ببساطة عن عدد m بحيث يكون لجميع السلاسل الثنائية${\displaystyle \sigma }$بطول m ،${\displaystyle \Gamma ^{\sigma }(n)}$يتقارب. يجب أن يوجد مثل هذا m وفقًا لفرضية كونيغ لأن${\displaystyle \Gamma }$يجب أن يكون كاملاً على جميع المسارات عبر${\displaystyle 2^{<\omega }}$. بمعرفة قيمة m كهذه، يصبح من السهل إيجاد جدول الحقيقة الفريد الذي يعطي${\displaystyle \Gamma ^{\sigma }(n)}$عند تطبيقها على${\displaystyle \sigma }$. يفشل الاتجاه الأمامي بسبب ضعف قابلية اختزال جدول الحقيقة.

• إتش. روجرز الابن ، 1967. نظرية الدوال التكرارية والحوسبة الفعالة ، الطبعة الثانية 1987، مطبعة معهد ماساتشوستس للتكنولوجيا. رقم ISBN 0-262-68052-1(غلاف ورقي)، رقم ISBN 0-07-053522-1