طيف الجملة

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

لتكن ψ جملة في منطق الرتبة الأولى . طيف ψ هو مجموعة الأعداد الطبيعية n التي يوجد لها نموذج محدود لـ ψ مكون من n عنصرًا.

إذا كانت مفردات ψ تتألف فقط من رموز علائقية، فيمكن اعتبار ψ جملة في منطق الرتبة الثانية الوجودي (ESOL) مُكمَّمة على العلاقات، أي على المفردات الفارغة. الطيف المعمم هو مجموعة نماذج جملة ESOL.

• طيف الصيغة من الدرجة الأولى

${\displaystyle \exists z,o~\forall a,b,c~\exists d,e}$

${\displaystyle a+z=a=z+a~\land ~a\cdot z=z=z\cdot a~\land ~a+d=z}$

${\displaystyle \land ~a+b=b+a~\land ~a\cdot (b+c)=a\cdot b+a\cdot c~\land ~(a+b)+c=a+(b+c)}$

${\displaystyle \land ~a\cdot o=a=o\cdot a~\land ~a\cdot e=o~\land ~(a\cdot b)\cdot c=a\cdot (b\cdot c)}$

يكون${\displaystyle \{p^{n}\mid p{\text{ prime}},n\in \mathbb {N} \}}$، مجموعة قوى العدد الأولي . في الواقع، مع${\displaystyle z}$ل${\displaystyle 0}$و${\displaystyle o}$ل${\displaystyle 1}$، هذه الجملة تصف مجموعة الحقول ؛ عدد عناصر الحقل المنتهي هو قوة عدد أولي.

• طيف صيغة المنطق من الدرجة الثانية الأحادية${\displaystyle \exists S,T~\forall x~\left\{x\in S\iff x\not \in T\land ~f(f(x))=x\land ~x\in S\iff f(x)\in T\right\}}$هي مجموعة الأعداد الزوجية . في الواقع،${\displaystyle f}$هو تقابل بين${\displaystyle S}$و${\displaystyle T}$، و${\displaystyle S}$و${\displaystyle T}$هي جزء من الكون. ومن ثم فإن عدد عناصر الكون زوجي.
• مجموعة المجموعات المنتهية والمنتهية جزئياً هي مجموعة أطياف منطق الرتبة الأولى مع علاقة الخلف.
• مجموعة المجموعات الدورية النهائية هي مجموعة أطياف منطق الرتبة الثانية الأحادي ذي الدالة الأحادية. وهي أيضاً مجموعة أطياف منطق الرتبة الثانية الأحادي ذي دالة الخلف.

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

وكنتيجة لذلك، أظهر جونز وسلمان أن المجموعة تنتمي إلى فئة التعقيد NE إذا كانت طيفًا. ^{[ 1 ]}

يتمثل أحد اتجاهات البرهان في إثبات أنه، لكل صيغة من الدرجة الأولى${\displaystyle \varphi }$، إن مشكلة تحديد ما إذا كان هناك نموذج لصيغة العدد n تعادل مشكلة تلبية صيغة متعددة الحدود في n ، والتي تقع في NP(n) وبالتالي في NE لمدخلات المشكلة (العدد n في شكل ثنائي، وهو سلسلة بحجم log( n )).

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

على سبيل المثال:

${\displaystyle \forall {x}\forall {y}\left(P(x)\wedge P(y)\right)\rightarrow (x=y)}$

بالنسبة لنموذج ذي عدد عناصر 2 (أي n = 2)، يتم استبداله بـ

${\displaystyle {\big (}\left(P(a_{1})\wedge P(a_{1})\right)\rightarrow (a_{1}=a_{1}){\big )}\wedge {\big (}\left(P(a_{1})\wedge P(a_{2})\right)\rightarrow (a_{1}=a_{2}){\big )}\wedge {\big (}\left(P(a_{2})\wedge P(a_{1})\right)\rightarrow (a_{2}=a_{1}){\big )}\wedge {\big (}\left(P(a_{2})\wedge P(a_{2})\right)\rightarrow (a_{2}=a_{2}){\big )}}$

ثم يتم استبدالها بـ ${\displaystyle {\big (}\left(p_{1}\wedge p_{1}\right)\rightarrow \top {\big )}\wedge {\big (}\left(p_{1}\wedge p_{2}\right)\rightarrow \bot {\big )}\wedge {\big (}\left(p_{2}\wedge p_{1}\right)\rightarrow \bot {\big )}\wedge {\big (}\left(p_{2}\wedge p_{2}\right)\rightarrow \top {\big )}}$

أين${\displaystyle \top }$هي الحقيقة،${\displaystyle \bot }$هذا زيف، و${\displaystyle p_{1}}$،${\displaystyle p_{2}}$هي متغيرات افتراضية. في هذه الحالة تحديدًا، تكون الصيغة الأخيرة مكافئة لـ${\displaystyle \neg (p_{1}\wedge p_{2})}$وهو أمر قابل للتنفيذ.

يتمثل الاتجاه الآخر للبرهان في إظهار أنه، لكل مجموعة من السلاسل الثنائية التي تقبلها آلة تورينج غير حتمية تعمل في وقت أسي (${\displaystyle 2^{cx}}$بالنسبة لطول الإدخال x)، توجد صيغة من الدرجة الأولى${\displaystyle \varphi }$بحيث تكون مجموعة الأرقام التي تمثلها هذه السلاسل الثنائية هي طيف${\displaystyle \varphi }$.

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

• طيف نظرية
• تحديد كمية العد

• فاجين، رونالد (1974). "الأطياف المعممة من الرتبة الأولى والمجموعات القابلة للتمييز في زمن متعدد الحدود" (ملف PDF) . في: كارب، ريتشارد م. (محرر). تعقيد الحساب . وقائع مؤتمر الرياضيات التطبيقية، وقائع SIAM-AMS. المجلد  7. الصفحات 27-41 . Zbl 0303.68035 .  
• غرادل، إريك؛ كولايتيس، فوكيون ج.؛ ليبكين، ليونيد ؛ مارتن، ماركس؛ سبنسر، جويل ؛ فاردي، موشيه ي.؛ فينيما، يدي؛ وينشتاين، سكوت (2007). نظرية النماذج المحدودة وتطبيقاتها . نصوص في علوم الحاسوب النظرية. سلسلة EATCS. ​​برلين: سبرينغر-فيرلاغ . doi : 10.1007/3-540-68804-8 . ISBN 978-3-540-00428-8. Zbl 1133.03001 . 
• إيمرمان، نيل (1999). التعقيد الوصفي . نصوص الدراسات العليا في علوم الحاسوب. نيويورك: سبرينغر-فيرلاغ. ص 113-119 . ISBN  0-387-98600-6. Zbl 0918.68031 . 
• دوراند، أرنو؛ جونز، نيل؛ ماركوفسكي، يوهان؛ مور، ماليكا (2012). "خمسون عامًا من مشكلة الطيف: دراسة استقصائية ونتائج جديدة". نشرة المنطق الرمزي . 18 (4): 505-553 . arXiv : 0907.5495 . Bibcode : 2009arXiv0907.5495D . doi : 10.2178/bsl.1804020 . S2CID 9507429 .