الطوبولوجيا الحاسوبية

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

• خوارزمية روبنشتاين وتومسون للتعرف على الكرة ثلاثية الأبعاد . تأخذ هذه الخوارزمية كمدخل مشعبًا ثلاثي الأبعاد مثلثيًا ، وتحدد ما إذا كان هذا المشعب متماثلًا شكليًا مع الكرة ثلاثية الأبعاد أم لا . يتميز زمن تشغيلها بأنه يتناسب طرديًا مع عدد الأشكال الرباعية الأوجه البسيطة في المشعب الثلاثي الأبعاد الأولي، كما أنه يستهلك ذاكرة ذات سعة متزايدة. وقد أثبت شاول شلايمر لاحقًا أن المشكلة تقع ضمن فئة التعقيد NP . ^{[ 4 ]} علاوة على ذلك، أثبت رافائيل زينتنر أن المشكلة تقع ضمن فئة التعقيد coNP، ^{[ 5 ]} بشرط صحة فرضية ريمان المعممة . وقد استخدم نظرية قياس الإنستانتون، ونظرية هندسة المشعبات ثلاثية الأبعاد، والعمل اللاحق لغريغ كوبربيرغ ^{[ 6 ]} حول تعقيد اكتشاف العقد.
• يتم أيضًا تنفيذ تحليل المجموع المتصل للمشعبات الثلاثية في Regina ، وله وقت تشغيل أسي ويعتمد على خوارزمية مماثلة لخوارزمية التعرف على الكرات الثلاثية.
• تم تحديد أن مشعب Seifert-Weber 3 لا يحتوي على سطح غير قابل للانضغاط بشكل خوارزمي بواسطة Burton و Rubinstein و Tillmann ^{[ 7 ]} واستند إلى نظرية السطح العادي.
• خوارزمية مانينغ هي خوارزمية لإيجاد البنى الزائدية على المشعبات ثلاثية الأبعاد التي تمتلك مجموعتها الأساسية حلاً لمسألة الكلمات . ^{[ 8 ]}

في الوقت الحالي، لم يتم تطبيق تحليل JSJ خوارزميًا في برامج الحاسوب. وكذلك تحليل الجسم المضغوط. توجد بعض الطرق الاستدلالية الشائعة والناجحة، مثل SnapPea ، التي حققت نجاحًا كبيرًا في حساب البنى الزائدية التقريبية على المشعبات ثلاثية الأبعاد المثلثية. من المعروف أن التصنيف الكامل للمشعبات ثلاثية الأبعاد يمكن إجراؤه خوارزميًا، ^{[ 9 ]} في الواقع، من المعروف أن تحديد ما إذا كان مشعبان ثلاثيا الأبعاد مغلقان وموجهان، مُعطيان بواسطة التثليثات (المجمعات التبسيطية)، متكافئين (متماثلين) هو عملية تكرارية بسيطة . ^{[ 10 ]} وهذا يعمم النتيجة المتعلقة بالتعرف على الكرات ثلاثية الأبعاد.

من المعروف أن تحديد ما إذا كانت العقدة تافهة أم لا يندرج ضمن فئات التعقيد NP ^{[ 12 ]} وكذلك co-NP ^{[ 13 ]} . وتُعدّ مشكلة تحديد جنس العقدة في فضاء ثلاثي الأبعاد مسألة NP-كاملة ^{[ 14 ]} ؛ ومع ذلك، فبينما يظل NP حدًا أعلى لتعقيد تحديد جنس العقدة في R³ ^أو S³ ^{، فإنه} حتى عام 2006 لم يكن معروفًا ما إذا كانت المشكلة الخوارزمية لتحديد جنس العقدة في تلك الفضاءات الثلاثية الأبعاد المحددة لا تزال مسألة NP-صعبة ^{[ 14 ]} .

• الأساليب الحسابية لمجموعات التماثل الكروي .
• الأساليب الحسابية لحل أنظمة المعادلات متعددة الحدود .
• لدى براون خوارزمية لحساب مجموعات التماثل للفضاءات التي هي مجمعات بوستنيكوف المحدودة ، ^{[ 15 ]} على الرغم من أنها لا تعتبر قابلة للتنفيذ على نطاق واسع.

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

• خوارزميات سميث العادية الفعالة والاحتمالية، كما هو موجود في مكتبة LinBox .
• اختزالات متماثلة بسيطة لمعالجة حسابات التماثل المسبقة، كما هو الحال في حزمة برامج بيرسيوس .
• خوارزميات لحساب التماثل المستمر للمركبات المفلترة ، كما هو الحال في حزمة TDAstats R. ^{[ 16 ]}
• في بعض التطبيقات، مثل تحليل البيانات الطوبولوجية (TDA)، من المفيد وجود ممثلين لفئات (التماثل) يكونون بأصغر حجم ممكن. تُعرف هذه المشكلة بمشكلة تحديد موقع (التماثل). على المشعبات المثلثية، عند إعطاء سلسلة تمثل فئة تماثل، يكون تقريب السلسلة المتماثلة ذات الدعم الأدنى عمومًا من المسائل الصعبة حسابيًا (NP-hard). ^{[ 17 ]} مع ذلك، فإن الحالة الخاصة بتقريب موقع التماثل الأحادي على المشعبات المثلثية الثنائية هي واحدة من ثلاث مسائل معروفة فقط تتساوى صعوبتها مع حدسية الألعاب الفريدة . ^{[ 18 ]}