دالة SSCG لفريدمان

دالة فريدمان SSCG هي دالة رياضية عرّفها هارفي فريدمان . وهي مُعرّفة بواسطة${\displaystyle {\text{SSCG}}(ك)}$باعتباره أكبر عدد صحيح${\displaystyle n}$بما يفي بما يلي:

هناك تسلسل${\displaystyle G_{1},\ldots ,G_{n}}$من الرسوم البيانية البسيطة شبه المكعبة بحيث يكون كل${\displaystyle G_{i}}$لديه على الأكثر${\displaystyle i+k}$الرؤوس ولعدم وجود${\displaystyle i<j}$يكون${\displaystyle G_{i}}$قابل للتضمين المتماثل في${\displaystyle G_{j}}$.

وفي وقت لاحق، قام فريدمان بتعريف الرسوم البيانية شبه المكعبة الأكثر عمومية${\displaystyle {\text{SCG}}(k)}$.

في الرياضيات ، وخاصة في نظرية المخططات ، يُعرف المخطط شبه المكعب البسيط ( SSCG ) بأنه مخطط بسيط محدود يكون لكل رأس فيه درجة لا تتجاوز ثلاثة. لنفترض أن لدينا سلسلة من المخططات شبه المكعبة البسيطة${\displaystyle G_{1}}$،${\displaystyle G_{2}}$... بحيث يكون كل رسم بياني${\displaystyle G_{i}}$لديه على الأكثر${\displaystyle i+k}$الرؤوس (لعدد صحيح ما)${\displaystyle k}$) وبدون${\displaystyle i<j}$يكون${\displaystyle G_{i}}$قابلة للتضمين المتماثل في (أي أنها جزء صغير من الرسم البياني لـ)${\displaystyle G_{j}}$.

تُثبت نظرية روبرتسون-سيمور أن الرسوم البيانية شبه المكعبة (بسيطة كانت أم لا) مرتبة ترتيبًا شبهيًا جيدًا بواسطة قابلية التضمين المتماثل، مما يعني أن مثل هذا التسلسل لا يمكن أن يكون لانهائيًا. ثم، بتطبيق ليمّة كونيغ على شجرة هذه التسلسلات تحت التمديد، لكل قيمة من${\displaystyle k}$توجد متتالية ذات طول أقصى. الدالة${\displaystyle {\text{SSCG}}(ك)}$يشير إلى طول الرسوم البيانية البسيطة شبه المكعبة. الدالة${\displaystyle {\text{SCG}}(k)}$يشير إلى طول الرسوم البيانية شبه المكعبة (العامة).

حدد هارفي فريدمان وظيفتين: SSCG و SCG.

عرّف فريدمان${\displaystyle {\text{SSCG}}(ك)}$باعتباره أكبر عدد صحيح${\displaystyle n}$تحقيق ما يلي: ^{[ 1 ]}

هناك تسلسل${\displaystyle G_{1},\ldots ,G_{n}}$من الرسوم البيانية البسيطة شبه المكعبة بحيث يكون كل${\displaystyle G_{i}}$لديه على الأكثر${\displaystyle i+k}$الرؤوس ولعدم وجود${\displaystyle i<j}$يكون${\displaystyle G_{i}}$قابل للتضمين المتماثل في${\displaystyle G_{j}}$.

الحدود القليلة الأولى من المتتالية هي

${\displaystyle \operatorname {SSCG} (0)=2,}$

${\displaystyle \operatorname {SSCG} (1)=5,}$ و

${\displaystyle \operatorname {SSCG} (2)=3\cdot 2^{3\cdot 2^{95}}\!\!-8=3\cdot 2^{118\,842\,243\,771\,396\,506\,390\,315\,925\,504}\!-8}$

${\displaystyle \qquad \qquad \;\approx \,3.241\,704\,229\cdot 10^{35\,775\,080\,127\,201\,286\,522\,908\,640\,065}}$

${\displaystyle \qquad \qquad \;\approx \,10^{3.5775\,\cdot \,10^{28}}.}$^{[ 2 ]}

لقد ثبت أن المصطلح التالي،${\displaystyle {\text{SSCG}}(3)}$، أكبر من TREE(3) . ^{[ 3 ]} أثبت فريدمان أن${\displaystyle {\text{SSCG}}(13)}$أكبر من زمن توقف أي آلة تورينج يمكن إثبات توقفها في Π ¹ ₁ -CA ₀ بحد أقصى${\displaystyle 2\uparrow \uparrow 2000}$^[أ] الرموز، وأنه لا يمكن إثبات وجودها في تلك النظرية بأقل من${\displaystyle 2\uparrow \uparrow 1000}$الرموز، حيث${\displaystyle \uparrow \uparrow }$يشير إلى التكرار . وقد فعل ذلك باستخدام فكرة مشابهة لتلك التي استخدمها في عبارة مماثلة أثبتها حول${\displaystyle {\text{TREE}}(3)}$[ ^{1 ]​}

لاحقًا، أدرك فريدمان أنه لا يوجد سبب وجيه لفرض شرط "البساطة" على الرسوم البيانية شبه المكعبة. فقام بتخفيف الشرط وتعريف${\displaystyle {\text{SCG}}(k)}$باعتبارها الأكبر${\displaystyle n}$مُرضٍ: ^{[ 4 ]}

هناك تسلسل${\displaystyle G_{1},\ldots ,G_{n}}$من الرسوم البيانية شبه المكعبة بحيث يكون كل${\displaystyle G_{i}}$لديه على الأكثر${\displaystyle i+k}$الرؤوس ولعدم وجود${\displaystyle i<j}$يكون${\displaystyle G_{i}}$قابل للتضمين المتماثل في${\displaystyle G_{j}}$.

الحد الأول من المتتالية هو${\displaystyle {\text{SCG}}(0)=6}$بينما المصطلح التالي${\displaystyle {\text{SCG}}(1)}$وهو أكبر من رقم غراهام . علاوة على ذلك،${\displaystyle {\text{SCG}}(3)}$أكبر من${\displaystyle {\text{TREE}}^{{\text{TREE}}(3)}(3)}$[ ^{3 ]​}

يدّعي آدم ب. غوشر أنه لا يوجد فرق نوعي بين معدلات النمو التقاربية لـ SSCG و SCG. ويكتب: "من الواضح أن${\displaystyle {\text{SCG}}(n)\geq {\text{SSCG}}(n)}$لكن يمكنني أيضاً إثبات ذلك${\displaystyle {\text{SSCG}}(4n+3)\geq {\text{SCG}}(n)}$[ ^{5 ]​}

• نظرية غودستين
• نظرية باريس-هارينغتون
• نظرية كاناموري-ماكالون
• نظرية كروسكال الشجرية ، التي تؤدي إلى دالة TREE مماثلة
• هيدرات

^{^} يكتب فريدمان هذا في الواقع على النحو التالي: 2^[2000]، والذي يشير إلى مكدس أسي من الرقم 2 بارتفاع 2000 باستخدام ترميزه. ^{[ 6 ]}