خوارزمية المجرة

من الأمثلة على الخوارزميات المجرة أسرع طريقة معروفة لضرب عددين ، ^{[ 4 ]} والتي تعتمد على تحويل فورييه ذي 1729 بُعدًا . ^{[ 5 ]} وهي تحتاج${\displaystyle O(n\log n)}$عمليات البت، ولكن نظرًا لكبر حجم الثوابت التي يخفيها ترميز Big O ، فإنه لا يُستخدم عمليًا. ومع ذلك، فإنه يُظهر أيضًا سبب إمكانية استمرار فائدة الخوارزميات الكونية. يقول المؤلفون: "نأمل أنه مع مزيد من التحسينات، قد تصبح الخوارزمية عملية للأعداد التي تحتوي على مليارات أو تريليونات من الأرقام فقط." ^{[ 5 ]}

اختبار AKS للأعداد الأولية هو اختبارٌ استثنائي. فهو الأكثر دقةً من الناحية النظرية بين جميع الخوارزميات المعروفة التي يمكنها تحديد ما إذا كان أي عدد أوليًا أم لا . على وجه الخصوص، يتميز هذا الاختبار بزمن حسابي متعدد الحدود ، وحتمية النتائج ، ودقة مطلقة . جميع الخوارزميات الأخرى المعروفة لا تفي بواحد على الأقل من هذه المعايير، ولكن أوجه القصور فيها طفيفة، وحساباتها أسرع بكثير، لذا تُستخدم بدلاً من AKS. في الواقع، يعمل اختبار ECPP أسرع بكثير من AKS، لكن لم يُثبت قط أنه يعمل بزمن حسابي متعدد الحدود. اختبار ميلر-رابين أسرع بكثير من AKS أيضًا، ولكنه يُنتج نتيجة احتمالية فقط. مع ذلك، يمكن تقليل احتمال الخطأ إلى قيم صغيرة جدًا (على سبيل المثال،${\displaystyle <10^{-100}}$يُعدّ هذا كافيًا للأغراض العملية. يوجد أيضًا إصدار حتمي من اختبار ميلر-رابين، يعمل في وقت متعدد الحدود على جميع المدخلات، لكن صحته تعتمد على فرضية ريمان المعممة (التي يُعتقد بها على نطاق واسع، ولكنها لم تُثبت). وجود هذه البدائل الأسرع (بكثير) يعني أن AKS لا يُستخدم عمليًا.

التحسين الأول مقارنةً بضرب المصفوفات بالقوة الغاشمة (الذي يستغرق${\displaystyle O(n^{3})}$كانت خوارزمية ستراسن (العمليات) هي خوارزمية تكرارية تأخذ${\displaystyle O(n^{2.807})}$العمليات. هذه الخوارزمية ليست مجرية وتُستخدم عمليًا. ومن التوسعات الأخرى لهذه الخوارزمية، باستخدام نظرية الزمر المتطورة ، خوارزمية كوبرسميث-وينوغراد وخلفائها الأفضل منها قليلًا، والتي تأخذ${\displaystyle O(n^{2.373})}$العمليات. هذه عمليات كونية - "ومع ذلك نؤكد أن هذه التحسينات ذات أهمية نظرية فقط، لأن الثوابت الضخمة المتضمنة في تعقيد ضرب المصفوفات السريع تجعل هذه الخوارزميات غير عملية عادةً." ^{[ 6 ]}

أظهر كلود شانون رمزًا بسيطًا ولكنه مثالي تقاربيًا يمكنه الوصول إلى السعة النظرية لقناة الاتصال . ويتطلب ذلك تعيين كلمة رمزية عشوائية لكل كلمة ممكنة.${\displaystyle n}$رسالة من نوع بت، ثم فك تشفيرها عن طريق إيجاد أقرب كلمة رمزية. إذا${\displaystyle n}$إذا تم اختيار حجم كبير بما يكفي، فإن هذا يتفوق على أي كود موجود ويمكن أن يقترب بشكل كبير من سعة القناة. لسوء الحظ، أي${\displaystyle n}$إن ابتكار خوارزميات كبيرة بما يكفي للتغلب على الخوارزميات الحالية أمر غير عملي تمامًا. ^{[ 7 ]} هذه الخوارزميات، رغم عدم استخدامها قط، ألهمت عقودًا من البحث في خوارزميات أكثر عملية يمكنها اليوم تحقيق معدلات قريبة جدًا من سعة القناة. ^{[ 8 ]}

مشكلة تحديد ما إذا كان الرسم البياني${\displaystyle G}$يتضمن${\displaystyle H}$تُعتبر المسألة الفرعية مسألة NP-كاملة بشكل عام، ولكن حيث${\displaystyle H}$إذا كانت ثابتة، فيمكن حلها في وقت متعدد الحدود. وقت التشغيل لاختبار ما إذا${\displaystyle H}$هو قاصر من${\displaystyle G}$في هذه الحالة هو${\displaystyle O(n^{2})}$[ ^{9 ]} حيث^​${\displaystyle n}$يمثل عدد الرؤوس في${\displaystyle G}$وتخفي صيغة Big O ثابتًا يعتمد بشكل فائق الأسي على${\displaystyle H}$الثابت أكبر من${\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2))))}$في تدوين كنوت للسهم العلوي ، حيث${\displaystyle h}$يمثل عدد الرؤوس في${\displaystyle H}$[ ^{10 ] حتى} في حالة${\displaystyle h=4}$لا يمكن حسابها بشكل معقول لأن الثابت أكبر من 2 مضروبًا في 4، أو 2 مضروبًا في 65536، أي${\displaystyle 2\uparrow \uparrow \uparrow 4={}^{65536}2=\underbrace {2^{2^{\cdot ^{\cdot ^{2}}}}} _{65536}}$.

في مصطلحات علم التشفير ، يُعرَّف "الاختراق" بأنه أي هجوم أسرع من حيث التوقع من هجوم القوة الغاشمة ، أي إجراء محاولة فك تشفير واحدة لكل مفتاح محتمل. بالنسبة للعديد من أنظمة التشفير، تُعرف عمليات الاختراق، لكنها لا تزال غير عملية باستخدام التقنيات الحالية. ومن الأمثلة على ذلك أفضل هجوم معروف ضد خوارزمية AES ذات 128 بت ، والذي يستغرق فقط${\displaystyle 2^{126}}$العمليات. ^{[ 11 ]} على الرغم من كونها غير عملية، إلا أن الفجوات النظرية يمكن أن توفر نظرة ثاقبة لأنماط الضعف، وتؤدي أحيانًا إلى اكتشاف الفجوات القابلة للاستغلال.

لعدة عقود، كان أفضل تقريب معروف لمسألة البائع المتجول في الفضاء المتري هو خوارزمية كريستوفيدس البسيطة للغاية ، والتي أنتجت مسارًا أطول بنسبة 50% على الأكثر من المسار الأمثل. ( عادةً ما كانت العديد من الخوارزميات الأخرى قادرة على تحقيق نتائج أفضل بكثير، ولكن لم يكن من الممكن إثبات ذلك بشكل قاطع). في عام 2020، تم اكتشاف خوارزمية أحدث وأكثر تعقيدًا بكثير يمكنها التفوق على هذه الخوارزمية.${\displaystyle 10^{-34}}$^[ 12 ^{] على الرغم من أن أحداً لن يتحول إلى هذه الخوارزمية لتحسينها الطفيف للغاية في} أسوأ الحالات، إلا أنها لا تزال تُعتبر مهمة لأن "هذا التحسين الضئيل يكسر الجمود النظري والنفسي على حد سواء". ^{[ 13 ]}

يمكن لخوارزمية واحدة، تُسمى "بحث هوتر"، حل أي مشكلة محددة جيدًا في وقت مثالي تقريبًا، مع مراعاة بعض الاستثناءات . تعمل هذه الخوارزمية من خلال البحث في جميع الخوارزميات الممكنة (من حيث وقت التشغيل)، وفي الوقت نفسه البحث في جميع البراهين الممكنة (من حيث طول البرهان)، بحثًا عن برهان صحة لكل خوارزمية. ولأن برهان الصحة ذو حجم محدود، فإنه "فقط" يُضيف ثابتًا ولا يؤثر على وقت التشغيل الأمثل. مع ذلك، فإن هذا الثابت كبير جدًا لدرجة تجعل الخوارزمية غير عملية تمامًا. ^{[ 14 ] [ 15 ]} على سبيل المثال، إذا كان أقصر برهان صحة لخوارزمية معينة بطول 1000 بت، فسيبحث البحث أولًا في ²⁹⁹⁹ برهانًا محتملًا آخر على الأقل.

يرتبط بحث هوتر باستقراء سولومونوف ، وهو صياغة رسمية للاستدلال البايزي . تُستخدم جميع النظريات القابلة للحساب (كما تُنفذها البرامج) التي تصف بدقة الملاحظات السابقة لحساب احتمالية الملاحظة التالية، مع إعطاء وزن أكبر للنظريات الأقصر. ومرة ​​أخرى، فإن البحث في جميع التفسيرات الممكنة يجعل هذه العملية شاملة للغاية.

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

تستطيع خوارزمية MST ذات الوقت الخطي المتوقع اكتشاف الشجرة الممتدة الدنيا للرسم البياني في${\displaystyle O(m+n)}$، أين${\displaystyle m}$هو عدد الحواف و${\displaystyle n}$يمثل عدد عقد الرسم البياني. ^{[ 20 ]} ومع ذلك، فإن العامل الثابت الذي تخفيه صيغة Big O ضخمٌ بما يكفي لجعل الخوارزمية غير عملية. يتوفر تطبيقٌ لها للعموم ^{[ 21 ]} ، وبالنظر إلى ثوابت التنفيذ المقدرة تجريبيًا، فإنها ستكون أسرع من خوارزمية بوروفكا فقط للرسوم البيانية التي يكون فيها${\displaystyle m+n>9\cdot 10^{151}}$[ ^{22 ]​}

توصل الباحثون إلى خوارزمية تحقق أفضل أداء ممكن ^{[ 23 ]} من حيث المفاضلة بين الوقت والمساحة في جداول التجزئة . ^{[ 24 ]} لكنها تبقى نظرية بحتة: "على الرغم من كفاءة جدول التجزئة الجديد غير المسبوقة، فمن غير المرجح أن يحاول أحد بناءه في أي وقت قريب. إنه معقد للغاية." ^{[ 25 ]} و"في الواقع، للثوابت أهمية بالغة. في العالم الحقيقي، يُعد عامل 10 سببًا لإنهاء اللعبة." ^{[ 25 ]}

الاتصال في الرسوم البيانية غير الموجهة (المعروف أيضًا باسم USTCON، اختصارًا لـ Undirected Source-Target CONnectivity) هو مشكلة تحديد ما إذا كان هناك مسار بين عقدتين في رسم بياني غير موجه، أو بعبارة أخرى، ما إذا كانتا في نفس المكون المتصل . عند استخدام${\displaystyle O({\text{N}})}$إذا سُمح باستخدام المساحة، فإن الحلول ذات الوقت متعدد الحدود مثل خوارزمية ديكسترا معروفة ومستخدمة منذ عقود. ولكن لسنوات عديدة، كان من غير المعروف ما إذا كان من الممكن القيام بذلك بشكل حتمي في${\displaystyle O({\text{log N}})}$الفضاء (الفئة L )، على الرغم من أنه كان من المعروف أنه ممكن باستخدام الخوارزميات العشوائية (الفئة RL ).

أظهرت ورقة بحثية رائدة نُشرت عام 2008 بقلم عمر رينغولد أن خوارزمية USTCON تنتمي بالفعل إلى فضاء L ، ^{[ 26 ]} مما يوفر خوارزمية ذات متطلبات مساحة أفضل تقاربياً. ومع ذلك، فإن الثابت الكبير جدًا للخوارزمية مخفيٌّ بسبب${\displaystyle O({\text{log N}})}$وهذا يعني أنه في أي مشكلة واقعية، فإنه يستهلك ذاكرة ووقت حساب أكثر بكثير من الطريقة المعروفة${\displaystyle O({\text{N}})}$الخوارزميات. على الرغم من عدم استخدامها عمليًا، إلا أن الورقة البحثية لا تزال علامة فارقة في النظرية، وقد تم الاستشهاد بها أكثر من 1000 مرة حتى عام 2026.

تُعدّ رموز التحقق من التكافؤ منخفضة الكثافة ، والمعروفة أيضًا باسم رموز LDPC أو رموز غالاغر، مثالًا على خوارزمية كانت ثورية عند تطويرها لأول مرة، لكنها أصبحت عملية مع تحسن الحوسبة. وقد ابتكرها روبرت ج. غالاغر في أطروحته للدكتوراه ^{[ 27 ]} في معهد ماساتشوستس للتكنولوجيا عام 1960. ^{[ 28 ] [ 29 ]} على الرغم من أن أداءها كان أفضل بكثير من الرموز الأخرى في ذلك الوقت، حيث وصلت إلى حد جيلبرت-فارشاموف للرموز الخطية ، إلا أن هذه الرموز تم تجاهلها إلى حد كبير لأن خوارزمية فك التشفير التكرارية الخاصة بها كانت مكلفة حسابيًا بشكل كبير بالنسبة للأجهزة المتاحة. ^{[ 30 ]}

تجدد الاهتمام برموز LDPC بعد اختراع رموز التوربو (1993)، التي تفوقت خوارزمية فك التشفير التكرارية الخاصة بها على الرموز الأخرى المستخدمة آنذاك. أُعيد اكتشاف رموز LDPC لاحقًا في عام 1996، ^{[ 31 ]} وأصبحت شائعة كبديل خالٍ من براءات الاختراع. ^{[ 32 ]} ورغم انتهاء صلاحية براءات اختراع رموز التوربو، فإن رموز LDPC لا تزال تتمتع ببعض المزايا التقنية، وتُستخدم في العديد من التطبيقات اليوم.

التثليث المضلعي هو تقسيم المضلع إلى مثلثات غير متداخلة. وقد أثبت برنارد شازيل في عام 1991 أنه يمكن تثليث أي مضلع بسيط في زمن خطي. ^{[ 33 ]} ومع ذلك، فإن الخوارزمية المقترحة معقدة للغاية، وهناك خوارزميات أبسط بكثير ^{[ 34 ]} ذات زمن شبه خطي.${\displaystyle O({\text{Nlog}}^{*}{\text{N}})}$تتوفر حلول الأداء، لذا يتم استخدامها بدلاً من ذلك. ^{[ 35 ]} "يمثل عمل [شازيل] إنجازًا نظريًا هامًا. ومع ذلك، فقد تبين أن خوارزميته ذات التعقيد الزمني O(n) صعبة البرمجة للغاية، وبالتالي، حسب علم المؤلفين، لا يوجد حتى الآن تطبيق عملي متاح." ^{[ 36 ]}