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

علم التعقيد الحسابي

• كثير حدود وكثير حدود غير قطعي
• NC = P
• NP = co-NP
• P = BPP
• P = PSPACE
• L = NL
• ما العلاقة بين كثير حدود غير قطعي و- BPP ?
• حدسية الألعاب الفريدة
• هل فرضية الوقت الأُسي صحيحة ؟
• هل يوجد دوال ذات اتجاه واحد ؟

خوارزميات

• ما هي اسرع خوارزمية لضرب عددين صحيحين بطول n بيت ؟
• ما هي اسرع خوارزمية لضرب مصفوفتين ؟
• أيوجد خوارزمية حدودية لمسألة التحليل لعوامل؟
• أيوجد خوارزمية بوقت حدودي لمسألة اللوغاريثم المتقطع ?
• أيوجد خوارزمية بوقت حدودي لمسألة تطابق المخطوطات ?

وصلات خارجية

• Major unsolved problems in theoretical computer science on StackExchange.
• Open problems around exact algorithms by Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397–405.
• Challenges for Theoretical Computer Science
• The Open Problems Project – open problems in هندسة رياضية حاسوبية and related fields.
• The RTA list of open problems – open problems in rewriting.
• The TLCA List of Open Problems – open problems in area typed lambda calculus.

موسوعات ذات صلة :

• موسوعة علم الحاسوب