قائمة بالمشاكل غير المحلولة في علوم الحاسوب

هذه المقالة عبارة عن قائمة بأبرز المشكلات غير المحلولة في علوم الحاسوب . تُعتبر المشكلة في علوم الحاسوب غير محلولة عندما لا يكون لها حل معروف أو عندما يختلف الخبراء في هذا المجال حول الحلول المقترحة.

• مشكلة P مقابل NP – تُعدّ مشكلة P مقابل NP سؤالًا رئيسيًا لم يُحلّ بعد في علوم الحاسوب، إذ تتساءل عمّا إذا كان بالإمكان حلّ أيّ مشكلة يُمكن التحقق من حلّها بسرعة بواسطة الحاسوب (NP) بسرعة أيضًا بواسطة الحاسوب (P). ولهذا السؤال آثارٌ بالغة الأهمية على مجالاتٍ مثل التشفير، وتصميم الخوارزميات، ونظرية الحوسبة. ^{[ 1 ]}
• ما هي العلاقة بين BQP و NP ؟
• مشكلة NC = P
• مشكلة NP = co-NP
• مسألة P = BPP
• مسألة P = PSPACE
• مسألة L = NL
• مشكلة PH = PSPACE
• مسألة L = P
• مسألة L = RL
• تخمين الألعاب الفريدة
• هل فرضية الزمن الأسي صحيحة؟
  • هل فرضية الزمن الأسي القوي (SETH) صحيحة؟
• هل توجد دوال أحادية الاتجاه ؟
  • هل التشفير باستخدام المفتاح العام ممكن؟
• تخمين رتبة السجل
• تخمين هارتمانيس-ستيرنز

• هل يمكن إجراء تحليل الأعداد الصحيحة إلى عواملها الأولية في وقت متعدد الحدود على جهاز كمبيوتر كلاسيكي (غير كمي)؟
• هل يمكن حساب اللوغاريتم المنفصل في وقت متعدد الحدود على جهاز كمبيوتر كلاسيكي (غير كمي)؟
• هل يمكن حساب أقصر متجه في شبكة في وقت متعدد الحدود على جهاز كمبيوتر كلاسيكي أو كمي؟
• هل يمكن حل مشكلة تماثل الرسوم البيانية في وقت متعدد الحدود على جهاز كمبيوتر كلاسيكي؟

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

• هل عملية تقنين الرسم البياني مكافئة لمسألة تماثل الرسم البياني في وقت متعدد الحدود؟
• هل يمكن التعرف على قوى الأوراق وقوى الأوراق من الرتبة k في وقت متعدد الحدود؟
• هل يمكن حل ألعاب التكافؤ في وقت متعدد الحدود؟
• هل يمكن حساب مسافة الدوران بين شجرتين ثنائيتين في وقت متعدد الحدود؟
• هل يمكن التعرف على الرسوم البيانية ذات عرض الزمرة المحدود في وقت متعدد الحدود؟ ^{[ 3 ]}
• هل يمكن إيجاد شبه جيوديسي مغلق بسيط على متعدد السطوح المحدب في وقت متعدد الحدود؟ ^{[ 4 ]}
• هل يمكن إيجاد تمثيل متزامن ذي حواف ثابتة لرسمين بيانيين معطيين في وقت متعدد الحدود؟ ^{[ 5 ]}
• هل يمكن حل مسألة مجموع الجذر التربيعي في وقت متعدد الحدود في نموذج آلة تورينج؟

• مسألة سكوليم : هل من الممكن تحديد ما إذا كان لمتتالية تكرارية خطية جبرية صفر؟
• المسألة العاشرة لهيلبرت على حقل الأعداد النسبية

• فرضية الأمثلية الديناميكية : هل للأشجار المتفرعة نسبة تنافسية محدودة؟
• هل يمكن إنشاء شجرة بحث بالعمق أولاً في NC ؟
• هل يمكن حساب تحويل فورييه السريع في زمن قدره o ( n log n ) ؟
• ما هي أسرع خوارزمية لضرب عددين مكونين من n رقم؟
• ما هو أقل تعقيد زمني ممكن في الحالة المتوسطة لخوارزمية Shellsort مع تسلسل فجوة ثابت حتمي؟
• هل يمكن حل مسألة 3SUM في وقت أقل من التربيعي بشكل كبير، أي في وقت O ( n ^2−ϵ ) لبعض ϵ > 0 ؟
• هل يمكن حساب مسافة التحرير بين سلسلتين نصيتين بطول n في وقت أقل من التربيعي بشكل كبير؟ (هذا ممكن فقط إذا كانت فرضية الوقت الأسي القوي خاطئة.)
• هل يمكن إجراء عملية فرز X + Y في زمن قدره o ( n ² log n ) ؟
• ما هي أسرع خوارزمية لضرب المصفوفات ؟
• هل يمكن حساب أقصر المسارات بين جميع الأزواج في وقت شبه مكعب قوي، أي في وقت O ( V ^3−ϵ ) لبعض ϵ > 0 ؟
• هل يمكن إزالة العشوائية من مبرهنة شوارتز-زيبيل لاختبار هوية كثيرات الحدود ؟
• هل تسمح البرمجة الخطية بخوارزمية ذات وقت متعدد الحدود قوي ؟ (هذه هي المسألة رقم 9 في قائمة مسائل سميل .)
• كم عدد الاستفسارات المطلوبة لتقطيع الكعكة دون حسد ؟
• ما هو التعقيد الخوارزمي لمسألة الشجرة الممتدة الدنيا ؟ وبصورة مكافئة، ما هو تعقيد شجرة القرار لمسألة الشجرة الممتدة الدنيا؟ الخوارزمية المثلى لحساب الأشجار الممتدة الدنيا معروفة ، لكنها تعتمد على أشجار القرار، لذا فإن تعقيدها غير معروف.
• تخمين جيلبرت-بولاك : هل نسبة شتاينر للمستوى الإقليدي تساوي${\displaystyle 2/{\sqrt {3}}}$؟

• تخمين باريندريخت-جيوفرز-كلوب : هل كل نظام نوع نقي ضعيف التطبيع يكون أيضًا قوي التطبيع؟

• هل يمكن تحديد منطق الضرب الأسي الخطي ؟
• هل فرضية أنديرا-كارب-روزنبرغ صحيحة؟
• تخمين تشيرني : إذا كان لدينا آلة حتمية محدودة مع${\displaystyle n}$تحتوي الولايات على كلمة تزامن ، فهل يجب أن يكون طولها على الأكثر${\displaystyle (n-1)^{2}}$؟
• مشكلة ارتفاع النجمة المعممة : هل يمكن التعبير عن جميع اللغات المنتظمة باستخدام التعبيرات المنتظمة المعممة ذات عمق التداخل المحدود لنجوم كلين ؟
• مشكلة فصل الكلمات : ما عدد الحالات المطلوبة في آلة حتمية محدودة تتصرف بشكل مختلف على سلسلتين معطيتين بطول${\displaystyle n}$؟
• ما هي حالة اكتمال تورينج لجميع الأوتوماتا الخلوية الأولية الفريدة ؟
• حدد ما إذا كان طول الكلمة الدنيا غير القابلة للإكمال لـ${\displaystyle M}$هي متعددة الحدود في${\displaystyle l(M)}$أو حتى في${\displaystyle sl(M)}$من المعروف أن${\displaystyle M}$يكون رمزًا متغير الطول إذا كان لكل${\displaystyle u_{1},...,u_{n},v_{1},...,v_{m}\in M}$،${\displaystyle u_{1}...u_{n}=v_{1}...v_{m}}$يشير إلى${\displaystyle n=m}$و${\displaystyle u_{i}=v_{i}}$للجميع${\displaystyle 0<i\leq n}$في مثل هذه الحالات، لا نعلم حتى الآن ما إذا كان هناك حدٌّ متعدد الحدود. وهذا يُعدّ إضعافًا محتملاً لتخمين ريستيفو (الذي تم دحضه بالفعل بشكل عام، على الرغم من أن الحدود العليا لا تزال مجهولة).
• حدد جميع الأعداد الصحيحة الموجبة${\displaystyle n}$بحيث يكون تسلسل${\displaystyle n}$و${\displaystyle n^{2}}$في القاعدة${\displaystyle b}$الاستخدامات الأكثر${\displaystyle k}$الأحرف المميزة، للثابتة${\displaystyle b}$و${\displaystyle k}$.

• قائمة بالمسائل غير المحلولة في الفيزياء
• قائمة بالمسائل غير المحلولة في الرياضيات

• Woeginger, Gerhard J. "Open problems around exact algorithms" . Discrete Applied Mathematics . 156 (2008): 397– 405.
• قائمة المشاكل المفتوحة في RTA - المشاكل المفتوحة في إعادة الصياغة .
• قائمة TLCA للمشاكل المفتوحة - المشاكل المفتوحة في مجال حساب التفاضل والتكامل اللامدا المكتوب .