مسألة كثير حدود وكثير حدود غير قطعي: الفرق بين النسختين
[نسخة منشورة] | [نسخة منشورة] |
تم حذف المحتوى تمت إضافة المحتوى
تعويض بـ قالب:شريط بوابات |
ط تدقيق إملائي يستهدف حروف الجر (المزيد) |
||
سطر 11:
تقديم الة تيورنج كان احد اهم الخطوات في جعل الحاسوب نموذجا رياضيا والاهم من هذا بات الان بقدرتنا على اعطاء تعريف دقيق للقسم او الصنف P والصنف NP , ولكن تنقص بعد التعريفات المهمة منها تعريف '''لغة الة تيورنج''' بشكل غير رسمي هي كل المُدخلات التي الة تيورنج تعطي جواب "نعم" , بشكل دقيق نعرفها كالتالي : فلتكن M الة تيورنج , ولنفرض أنَّ <math>\Sigma</math> هي ابجدية الالة , حينها نعرف لغة الالة كالتالي: <math> L(M)=\{x\in \Sigma^* : M(x)=1\} </math> .
امر اخر مهم جدا هو نجاعة الخوارزمية , وفي هذه الحالة النجاعة هي كمية الوقت التي تستخدمها الخوارزمية حتى الوصول لنتيجة , وبشكل دقيق : فلتكن <math> f:\mathbb{N} \to \mathbb{N} </math> دالة من الاعداد الطبيعية
من التعريفين السابقين صيغة المسألة بشكل دقيق ستكون كالتالي : نعرف P لتكون <math> \cup_{c>0} DTIME[n^c] </math> , ونعرف NP ليكون <math> \cup_{c>0} NTIME[n^c] </math> , والسؤال هو هل هاتين المجموعتين مساويتان ؟
سطر 24:
اما الصفة الاولى فقد نبعت من كون مجال بحث المسألة "كبير جدا" وكذلك لان لا احد نجح بالاتيان بخوارزمية لحلها , مثلا مسألة الاكتفاء : معطى صيغة بوليانية ونريد ان نعرف هل قابلة للاكتفاء , الطريقة الوحيدة هي كتابة كل التعويضات الممكنة للمتغيرات وفحصها هل تكفي الصيغة ام لا , هذه الخوارزمية من افضل الخوارزميات لهذه المسألة للان ولكن هذه الخوارزمية تعبر على كل مجال البحث وهذا يعني انها ستعبر على <math>O(2^n)</math> , هذه الدالة الأُسية عندما يكون n=80 حينها لو انك عشت من اول خلق الكون ليومنا ما انتهت من البحث !
اما الصفة الثانية فهي تحتاج
مصطلح الاختصار فتح باباً لتكون لتعريف متى المسائل مطابقة (مع فارق وقت حدودي) , لذا فاننا نعرف المسائل NP كاملة لتكون كل المسائل التي تتبع NP ويمكن اختصار كل المسائل في NP لهذه المسألة , من الوهلة الاولى لا يبدو ان هذه المسائل موجودة وذلك لقوتها الهائلة وذلك لان حلها يعني ان تكون قادرا على حل كثير من المسائل , ولكن المفاجأة انه يوجد مسائل كهذه وهي شائعة وكثيرة ولها كثير من التطبيقات العملية تنبسط على كل مجالات علم الحاسوب تقريبا , ولكن هل يمكن ان نحل هذه المسائل بنجاعة ؟ لا نعرف , وذلك لان هذا السؤال مساوي ومكافئ للسؤال هل NP=P . وبالتحديد يمكن حلها بنجاعة فقط اذا P=NP .
سطر 32:
==توابع جواب الحدسية==
هناك حالتين :
# NP=P , وهذا سيغير الحياة التي سنعرفها
# اما اذا NP≠P فهي اكثر منطقية من توابع الاولى اذ انه ما كنا نعتقد انه صعب فهو حتما كذلك وكل ما تطور من نظريات ووسائل في الثلاثين عاما الاخيرة كانت مفيدة جدا في تقدم العالم .
|