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