نظرية التعقيد الوصفي

في تعقيد الدوائر ، يمكن إثبات أن منطق الرتبة الأولى مع المسندات العشوائية يساوي AC ⁰ ، وهو الصنف الأول في التسلسل الهرمي AC . في الواقع، هناك ترجمة طبيعية من رموز منطق الرتبة الأولى إلى عقد الدوائر، مع${\displaystyle \forall ,\exists }$كون${\displaystyle \land }$و${\displaystyle \lor }$بحجم n . يُميّز منطق الرتبة الأولى في توقيع ذي مسندات حسابية تقييد عائلة دوائر AC ^{0 بتلك التي يمكن بناؤها في} زمن لوغاريتمي متناوب . ^{[ 2 ]} يتوافق منطق الرتبة الأولى في توقيع ذي علاقة ترتيب فقط مع مجموعة اللغات الخالية من النجوم . ^{[ 10 ] [ 11 ]}

يكتسب منطق الرتبة الأولى قدرة تعبيرية كبيرة عند إضافة عامل إليه لحساب الإغلاق المتعدي لعلاقة ثنائية. ومن المعروف أن منطق الإغلاق المتعدي الناتج يُميّز الفضاء اللوغاريتمي غير الحتمي (NL) على البنى المرتبة. وقد استخدم إيمرمان هذا لإثبات أن NL مغلق تحت المكمل (أي أن NL = co-NL). ^{[ 12 ]}

عند تقييد عامل الإغلاق المتعدي بالإغلاق المتعدي الحتمي ، فإن المنطق الناتج يصف بدقة الفضاء اللوغاريتمي على الهياكل المرتبة.

في الهياكل التي لها دالة لاحقة، يمكن أيضًا وصف NL بواسطة صيغ كروم من الدرجة الثانية .

SO-Krom هي مجموعة الاستعلامات المنطقية القابلة للتعريف بصيغ من الدرجة الثانية في شكلها الطبيعي الاقتراني ، بحيث تكون مُكمِّمات الدرجة الأولى شاملة، ويكون الجزء الخالي من المُكمِّمات في الصيغة بصيغة Krom، مما يعني أن صيغة الدرجة الأولى هي اقتران لفصل، وفي كل "فصل" يوجد متغيران على الأكثر. كل صيغة Krom من الدرجة الثانية تُكافئ صيغة Krom وجودية من الدرجة الثانية.

يصف SO-Krom NL على الهياكل ذات وظيفة لاحقة. ^{[ 13 ]}

يُعدّ FO[LFP] امتدادًا لمنطق الرتبة الأولى بواسطة مُعامل النقطة الثابتة الصغرى، الذي يُعبّر عن النقطة الثابتة للتعبير الرتيب. يُضيف هذا إلى منطق الرتبة الأولى القدرة على التعبير عن الاستدعاء الذاتي. تُبيّن نظرية إيمرمان-فاردي، التي أثبتها إيمرمان وفاردي بشكل مستقل ، أن FO[LFP] يُميّز PTIME على البنى المرتبة. ^{[ 14 ] [ 15 ]}

اعتبارًا من عام 2025، ولا يزال من غير الواضح ما إذا كان هناك منطق طبيعي يميز PTIME على الهياكل غير المرتبة.

تنص نظرية أبيتبول -فيانو على أن FO[LFP]=FO[PFP] على جميع البنى إذا وفقط إذا كان FO[LFP]=FO[PFP]؛ وبالتالي إذا وفقط إذا كان P=PSPACE. وقد تم تعميم هذه النتيجة لتشمل نقاطًا ثابتة أخرى. ^{[ 8 ]}

في حالة وجود دالة لاحقة، يمكن أيضًا وصف PTIME بواسطة صيغ هورن من الدرجة الثانية.

SO-Horn هي مجموعة من الاستعلامات المنطقية القابلة للتعريف باستخدام صيغ SO في شكل عادي منفصل بحيث تكون جميع المحددات الكمية من الدرجة الأولى عالمية ويكون الجزء الخالي من المحددات الكمية من الصيغة في شكل Horn ، مما يعني أنها AND كبيرة لـ OR، وفي كل "OR" يتم نفي كل متغير باستثناء متغير واحد محتمل.

هذه الفئة تساوي P على الهياكل ذات دالة لاحقة. ^{[ 16 ]}

يمكن تحويل هذه الصيغ إلى صيغ prenex في منطق هورن الوجودي من الدرجة الثانية. ^{[ 13 ]}

كان برهان رونالد فاجين عام 1974 على أن فئة التعقيد NP تتميز تحديدًا بفئات البنى القابلة للتأصيل في منطق الرتبة الثانية الوجودي نقطة انطلاق نظرية التعقيد الوصفي. ^{[ 6 ] [ 17 ]}

بما أن مكمل الصيغة الوجودية هو صيغة شاملة، فإنه يترتب على ذلك مباشرة أن co-NP يتميز بمنطق الرتبة الثانية الشامل. ^{[ 6 ]}

لذا، فإن منطق الرتبة الثانية غير المقيد يساوي التسلسل الهرمي متعدد الحدود PH . وبشكل أدق، لدينا التعميم التالي لنظرية فاجين: مجموعة الصيغ في الشكل الطبيعي المسبق حيث تتناوب الكميات الوجودية والكلية من الرتبة الثانية k مرة لتوصيف المستوى k من التسلسل الهرمي متعدد الحدود. ^{[ 18 ]}

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

يمكن تمييز فئة جميع المسائل القابلة للحساب في الفضاء متعدد الحدود، PSPACE ، من خلال زيادة منطق الرتبة الأولى باستخدام عامل نقطة ثابتة جزئية أكثر تعبيرًا.

المنطق الجزئي ذو النقطة الثابتة ، FO[PFP]، هو امتداد لمنطق الرتبة الأولى مع عامل النقطة الثابتة الجزئية، والذي يعبر عن النقطة الثابتة للصيغة إذا كانت موجودة ويعيد "خطأ" خلاف ذلك.

تتميز PSPACE على الهياكل المرتبة بمنطق النقطة الثابتة الجزئية . ^{[ 20 ]}

يمكن توسيع منطق الرتبة الثانية باستخدام عامل إغلاق متعدٍّ بنفس طريقة منطق الرتبة الأولى، مما ينتج عنه SO[TC]. يمكن لعامل الإغلاق المتعدّي الآن أن يأخذ متغيرات من الرتبة الثانية كوسيط. يُميّز SO[TC] فضاء PSPACE . بما أن الترتيب يُمكن الإشارة إليه في منطق الرتبة الثانية، فإن هذا التمييز لا يفترض وجود هياكل مُرتبة. ^{[ 21 ]}

نُعرّف المتغيرات ذات الرتبة العليا. المتغير من الرتبة${\displaystyle i>1}$لديه رتبة${\displaystyle k}$ويمثل أي مجموعة من${\displaystyle k}$- مجموعات من عناصر مرتبة${\displaystyle i-1}$تُكتب هذه الصيغ عادةً بأحرف كبيرة، مع استخدام عدد طبيعي كأسّ للدلالة على رتبتها. منطق الرتبة العليا هو مجموعة صيغ الرتبة الأولى التي نضيف إليها التحديد الكمي لمتغيرات الرتبة العليا؛ لذا سنستخدم المصطلحات المُعرّفة في مقالة الرتبة الأولى دون إعادة تعريفها.

هو${\displaystyle ^{i}}$هي مجموعة الصيغ التي تحتوي على متغيرات من الرتبة على الأكثر${\displaystyle i}$HO${\displaystyle _{j}^{i}}$هي مجموعة فرعية من الصيغ من الشكل${\displaystyle \phi =\exists {\overline {X_{1}^{i}}}\forall {\overline {X_{2}^{i}}}\dots Q{\overline {X_{j}^{i}}}\psi }$، أين${\displaystyle Q}$هو مُكمِّم و${\displaystyle Q{\overline {X^{i}}}}$هذا يعني أن${\displaystyle {\overline {X^{i}}}}$هو عبارة عن مجموعة من المتغيرات من الرتبة${\displaystyle i}$بنفس الكمية. لذا HO${\displaystyle _{j}^{i}}$هي مجموعة الصيغ التي${\displaystyle j}$تناوب محددات الكمية للترتيب${\displaystyle i}$، بدءًا من${\displaystyle \exists }$، متبوعًا بصيغة من الرتبة${\displaystyle i-1}$.

باستخدام الترميز القياسي للرباعية ،${\displaystyle \exp _{2}^{0}(x)=x}$و${\displaystyle \exp _{2}^{i+1}(x)=2^{\exp _{2}^{i}(x)}}$.${\displaystyle \exp _{2}^{i+1}(x)=2^{2^{2^{2^{\dots ^{2^{x}}}}}}}$مع${\displaystyle i}$أوقات${\displaystyle 2}$

كل صيغة من صيغ الطلب${\displaystyle i}$هذا يكافئ صيغة في الشكل الطبيعي السابق، حيث نكتب أولاً التحديد الكمي على متغير من${\displaystyle i}$الرتبة ثم صيغة الرتبة${\displaystyle i-1}$في شكلها الطبيعي.

تُعادل HO فئة الدوال الأولية ELEMENTARY . بتعبير أدق،${\displaystyle {\mathsf {HO}}_{0}^{i}={\mathsf {NTIME}}(\exp _{2}^{i-2}(n^{O(1)}))}$، بمعنى برج من${\displaystyle (i-2)}$ ٢، تنتهي بـ${\displaystyle n^{c}}$، أين${\displaystyle c}$ثابت. وحالة خاصة من ذلك هي أن${\displaystyle \exists {\mathsf {SO}}={\mathsf {HO}}_{0}^{2}={\mathsf {NTIME}}(n^{O(1)})={\color {Blue}{\mathsf {NP}}}}$وهذا هو بالضبط ما تنص عليه نظرية فاجين . باستخدام آلات أوراكل في التسلسل الهرمي متعدد الحدود ،${\displaystyle {\mathsf {HO}}_{j}^{i}={\color {Blue}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{O(1)})^{\Sigma _{j}^{\mathsf {P}}})}$