نظرية التعقيد هي فرع من فروع نظرية الحوسبة في علم الحاسوب النظري والرياضيات وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وكذلك تُعنى في ربط أقسام التعقيد (complexity classes) ببعضها , والمسألة الحاسوبية هي مسألة التي الحاسوب قادر على حلها .
ويمكن اعتبار مسألة صعبة اذا استخدمت كمية مُعينة من الموارد ,ايا كانت, مهما كانت الخوارزمية. ولعل النماذج الحسابية هي الطريقة الأمثل في هذه النظرية لدراسة هذه المسائل وتحديد كمية الموارد اللازمة مثل : الوقت او كمية المكان الاضافي اللازم . ويوجد كذلك معايير تعقيد اخرى مثل : الاتصال(مستخدم في نظرية تعقيد الاتصال) وعدد البوابات في الدارات المنطقية ( مُستخدم في نظرية تعقيد الدارات المنطقية ) وكذلك عدد المعالجات (مستخدم في الحساب المتوازي ) . وأحد اهم اساسات نظرية التعقيد الحسابي هي تبيين الحدود العملية لما يستطيع الحاسوب القيام به وما لا يستطيع القيام به .
المجالات القريبة في علم الحاسوب النظري هي تحليل الخوارزميات ونظرية الحاسوبية . ولعل الاختلاف بين تحليل الخوارزميات ونظرية التعقيد الحسابية هو أن الأول يسأل عن خوارزمية معينة لحل مسألة بينما الاخر يسأل عن كل الخوارزميات التي يمكنها حل المسألة وبالتحديد فان الأخير يحاول تصنيف المسائل التي يمكن حلها او عدم حلها بوضع كمية مُحددة من الموارد , اما وضع الحدود للموارد الموجودة هو ما يميز نظرية التعقيد الحسابي عن نظرية الحاسوبية اي أن نظرية الحاسوبية تسأل عن اية مسائل يمكن حلها(او عدم حلها) بواسطة خوارزمية .
محتويات [أخف]
1 مسائل , مُدخل وطول المُدخل
1.1 تعريف المُدخل
1.2 لغات او مسائل التقرير
1.3 مسائل دالة
1.4 قياس تعقيد الخوارزمية
2 نماذج حاسوبية ومقاييس التعقيد
2.1 نماذج حاسوبية
2.2 قياس التعقيد
2.3 تعقيد الحالة الأفضل والحالة الأسوأ وتعقيد الحالة المتوسطة
2.4 حدود عليا وحدود دنيا على تعقيد المسائل
3 اقسام تعقيد
3.1 تعريف
3.2 اقسام تعقيد مهمة
3.3 مسائل كاملة
3.3.1 مبرهنة كوك وليفين
3.4 مبرهنات الهرمية
4 الاختصار
5 مسائل غير محلولة
5.1 مسألة NP-P
5.2 مسائل التي لا تتبع P ولا تتبع NP كاملة
6 أنظر أيضا
7 مصادر
مسائل , مُدخل وطول المُدخل[عدل]
تعريف المُدخل[عدل]
بشكل عام مُدخل(instance) لمسألة حاسوبية هو مجموعة معطيات x_1,\cdots,x_d والمسألة الحاسوبية هي حساب دالة متعلقة بهذه المعطيات . مثال حساب المُحدد المُدخلات لهذه المسألة هي القيم في المصفوفة والمُخرج هو المُحدد . وقد يُنظر إلى المسألة على انها مجموعة كل المدخلات والمُخرج الملائم للمُدخل . أما انه يمكن ان تكون المدخلات بأطوال مختلفة وطول المُدخل هو كمية البتات اللازمة لترميز المُدخل بشكل ملائم اي أن المُدخل يكون سلسلة (string) تابعة ل- \{0,1\}^* مثال يمكن ترميز العدد (مثال 15 ) بواسطة تمثيله بنظام العد الثنائي ( الترميز الملائم ل-15 هو 1111),مثال اخر هو ترميز مخطط والذي يمكن ترميزه بواسطة القيم في المصفوفة الملائمة له .
لغات او مسائل التقرير[عدل]
مسألة التقرير هي نوع خاص من المسائل الحاسوبية التي جوابها يكون إما نعم او لا او 0 و- 1 وهذا النوع من المسائل يُعرف أيضا باللغات في حين أن الأعضاء التابعة لهذه اللغة هي المُدخلات التي جوابها نعم . والهدف يكون باعطائنا مُدخل يجب التقرير اذا ما المُدخل عضو في هذه اللغة او لا وذلك بواسطة خوارزمية , مثال : فلتكن مسألة تقرير اذا ما عدد معطى هو أولي اللغة هي كل الاعداد الاولية ولتقرير اذا ما مُدخل معين هو أولي نشغل الخوارزمية التالية : "فحص كل الاعداد من 2 حتى هذا العدد وفحص اذا ما هذا العدد يمكن يقبل القسمة على اي عدد غير نفسه اذا نعم فالعدد ليس اوليا وخلاف ذلك العدد اولي" .
مسائل دالة[عدل]
مسائل دالة(function problem) هي مسائل التي لكل مُدخل يكون هنالك مُخرج وحيد وتختلف هذه المسائل عن مسائل التقرير في انها قد يكون مُخرجها غير الاجابة بنعم ولا . مثال : تحليل لعوامل اولية ,المُدخل هو عدد المخرج هو التحليل لعوامل لهذا العدد . وقد يُعتقد أن مسائل الدالة اغنى من مسائل التقرير ولكن هذا غير صحيح بالضرورة اذ انه يمكن تحويل كل مسألة دالة لمسألة تقرير مثال : تحليل لعوامل اولية , المدخل : عدد , x, وقائمة اعداد, x1,x2,...,xd والمخرج هو نعم فقط اذا حاصل ضرب الاعداد هو ,x, وبالاضافة كل عدد بالقائمة هو اولي .
قياس تعقيد الخوارزمية[عدل]
لقياس صعوبة مسألة حاسوبية , وَجَب على المرئ ان يقيس الوقت اللازم لافضل خوارزمية تحل المسألة . وبشكل عام الوقت قد يرتبط بطول المُدخل وبالتحديد مُدخلات طويلة حتما ستحتاج اكثر وقت للوصول للحل ,لذا فان قياس الوقت اللازم لحل مسألة هو دالة بطول المُدخل , وبشكل عام طول المُدخل يكون بالبتات . لذا فان علم التعقيد بالاساس يبحث مدى قابلية توسع الخوارزمية .
فلنفرض أنَّ n هو طول المُدخل حينها الوقت اللازم للخوارزمية يمكن التعبير عنه بواسطة n , وبما أنَّ لكل مُدخل قد يكون الوقت اللازم لحل المسألة مختلف لذا فانه يُأخذ بالاعتبار تعقيد وقت الحالة الأسوأ , (T(n , والذي هو الوقت الاطول الذي ستحتاجه الخوارزمية بالنسبة لكل المُدخلات . اذا كان (T(n متعدد الحدود اي : يوجد ثابت c>0 بحيث أنَّ (T(n)=O(nc حينها نقول أنَّ الخوارزمية وقتها متعددة الحدود (polynomial time algorithm) . اطروحة كوبهام تقترح أن مسألة يمكن حلها مع كمية معقولة من الموارد اذا يوجد خوارزمية تحلها بوقت متعدد الحدود .
نماذج حاسوبية ومقاييس التعقيد[عدل]
نماذج حاسوبية[عدل]
وهي محاكاة نظرية لفكرة الحاسوب اي أنَّ النموذج الحاسوبي هو الة التي تقوم بعمليات اساسية (قد تختلف من نموذج لاخر) ونظرية التعقيد تسأل عن مجموعة العمليات الأصغر التي يمكنها حل المسألة , اكثر النماذج شيوعا في نظرية التعقيد هي الة تيورنج وهي الة حاسوبية تعالج رموز مكتوبة على شريط العمليات وهذا النموذج قد لا يكون عملي ولكن هناك ايمان اذا ما مسألة يمكن حلها بواسطة خوارزمية حينها توجد الة تيورنج التي يمكنها حل المسألة , وهذه كانت المقال الاساسي في اطروحة تشيرش-تيورنج . وحسب ما هو معلوم كل ما يمكن حسابه بواسطة نماذج اخرى يمكن حسابه كذلك بواسطة الة تيورنج . ولهذا السبب فان هذه الالة هي الاكثر شيوعا في نظرية التعقيد .اكثر النماذج الحاسوبية المستخدمة هي :
آلة تورنج
الة سجل
الأوتومات غير المنتهي ذو المكدس
آلة الحالات المحدودة
قياس التعقيد[عدل]
ولكي يكون قياس التعقيد , والذي هو استخدام كمية مُعينة من الموارد مثل : الوقت او المكان , دقيقا ومُعرفا بشكل رياضياتي سليم كانت الحاجة للنماذج الحاسوبية مثال : الة تيورنج , وقد نعرف الوقت اللازم لحل مسألة بواسطة الة تيورنج ,M , مع المدخل للالة ,x, هو عدد الخطوات او التحول من وضعية لوضعية اللازمة للالة حتى التوقف والاتيان بالنتيجة ( مثل : نعم او لا ) . ونقول أنَّ الة تيورنج , M , وقت عملها هو (f(n اذا كان الوقت اللازم للالة M على كل مُدخل طولة n هو (f(n . ونقول أنَّ مسألة يمكن حلها بوقت (f(n اذا يوجد الة تيورنج M الوقت الذي تحتاجه لحل مُدخل طوله n هو (f(n . وبما أنَّ نظرية التعقيد اهتمامها بتصنيف المسائل حسب صعوبتها لذا فالمرئ يمكنه تعريف مجموعة مسائل تحقق معيار مُعين مثال ذلك المجموعة ((DTIME(f(n وهي مجموعة المسائل التي يوجد الة تيورنج قطعية التي تحلها بوقت (f(n .
هنالك عدة مقاييس للتعقيد ولعل اهمها هو الوقت والمكان , ولعل بديهيات بلم (Blum axioms) في نظرية التعقيد تُعرف هذه المقاييس . مقاييس اخرى مُستخدمة في نظرية التعقيد هي تعقيد الاتصال وتعقيد الدارات المنطقية وتعقيد شجرة التقرير . وبشكل عام في قياس تعقيد الخوارزميات شاع استخدام رمز O الكبير .
تعقيد الحالة الأفضل والحالة الأسوأ وتعقيد الحالة المتوسطة[عدل]
تعقيد الحالة الأفضل والحالة الأسوأ والمتوسطة هي ثلاث طرق مختلفة لقياس تعقيد الوقت (او اي مقياس اخر) لمُدخلات مُختلفة من نفس الطول , وبما أنه باختلاف المُدخلات قد تكون بعض المُدخلات حلها اسرع من الاخريات لذا نعرف التالي :
تعقيد الحالة الأفضل : وهو الوقت اللازم لحل مُدخل مسألة حيث أن هذا المُدخل يستلزم اقل وقت من بين كل المُدخلات المحتملة التي لها نفس الطول .
تعقيد الحالة الأسوأ : وهو الوقت اللازم لحل مُدخل مسألة حيث أن هذا المُدخل يستلزم اكثر وقت من بين كل المدخلات المحتملة التي لها نفس الطول .
تعقيد الحالة المتوسطة : وهو متوسط الوقت اللازم لحل كل المدخلات التي لها نفس الطول , وهذا التعقيد يمكن حسابه فقط بعد ان نفرض توزيع الاحتمال على المُدخلات .
حدود عليا وحدود دنيا على تعقيد المسائل[عدل]
لكي نصنف الوقت الحسابي للمسائل (اي الوقت اللازم لحل مسألة بواسطة نموذج حاسوبي مُعين) المرئ وجب عليه ان يبرهن الحدود الدنيا والعليا لكمية الوقت الاقل التي تستلزمها افضل خوارزمية لحل المسألة , وبشكل عام تعقيد الخوارزمية هو تعقيد الحالة الأسوأ الا اذا حُدد غير ذلك , ولكي نبرهن أن لمسألة حد أعلى (T(n وجب تبيين خوارزمية التي تستلزم وقت (T(n . ولكن لكي نبرهن حد ادنى المهمة اصعب بكثير اذ على المرئ أن يبين ان كل خوارزمية ممكنة لحل المسألة لا يوجد أي منها وقتها اقل من (T(n . وللتوضيح : عندما نقول " كل خوارزمية " نعني أنه لا يمكن أن يكون هناك خوارزمية التي تستلزم وقتا اقل من (T(n حتى في المستقبل . والحدود الدنيا والعليا لمسألة يُعبر عنها بواسطة رمز O كبير .
اقسام تعقيد[عدل]
تعريف[عدل]
قسم تعقيد هو مجموعة مسائل التي لها نفس التعقيد , وقد تعرف اقسام التعقيد حسب العوامل التالية :
نوع المسألة الحاسوبية : وفي هذا الباب نوع المسألة الاكثر شيوعا هي مسألة التقرير ولكن هنالك أيضا انواع اخرى مثل مسائل دالة , مسائل عد , مسائل استمثال او مسائل وعد ...
نموذج الحاسوبية : ولعل الاكثر شيوعا هي الة تيورنج القطعية ولكن هنالك استخدام لالة تيورنج غير القطعية , دارات منطقية , الة تيورنج كمومية,...
الموارد التي يتم حصرها والحدود : مثل وقت متعدد الحدود , مكان لوغارثمي , عمق ثابت , ...
هنالك تصنيفات اكثر تعقيدا من هذه المذكورة هنا مثل الة تيورنج احتمالية , الالات تيورنج تفاعلية , مسائل اتصال , ...
اقسام تعقيد مهمة[عدل]
كثير من اقسام التعقيد يمكن تعريفها بواسطة تحديد الوقت او المكان التي تستخدمها الخوارزمية وفي هذا السياق يمكن تعريف بعض الاقسام كالتالي :
اقسام تعقيد النموذج الحاسوبي قيود الموارد
((DTIME(f(n الة تيورنج قطعية وقت (f(n
P الة تيورنج قطعية وقت (poly(n
EXPTIME الة تيورنج قطعية وقت(2poly(n
((NTIME(f(n الة تيورنج غير قطعية وقت (f(n
NP الة تيورنج غير قطعية وقت (poly(n
NEXPTIME الة تيورنج غير قطعية وقت (2poly(n
((DSPACE(f(n الة تيورنج قطعية مكان (f(n
L الة تيورنج قطعية مكان (O(log n
PSPACE الة تيورنج قطعية مكان (poly(n
EXPSPACE الة تيورنج قطعية مكان (2poly(n
((NSPACE(f(n الة تيورنج غير قطعية مكان (f(n
NL الة تيورنج غير قطعية مكان (O(log n
NPSPACE الة تيورنج غير قطعية مكان (poly(n
NEXPSPACE الة تيورنج غير قطعية مكان (2poly(n
لقد تبين أنَّ NSPACE(f(n))\subseteq DSPACE(f^2(n)) وكذلك : PSPACE=NPSPACE و EXPSPACE=NEXPSPACE وهذا كله بواسطة مبرهنة سافيتش (Savitch theorem) .
اقسام مهمة اخرى من ضمنها ZPP , BPP ,Co-RP,RP وهي تستخدم الة تيورنج احتمالية في تعريفها , اما BQP و- QMA ففيهما استخدم الة تيورنج كمومية اما NC و- AC وكذلك P/Poly تعرف بواسطة الدارات المنطقية اما بالنسبة ل-P# فهو قسم مسائل عد واحد اهمها على الإطلاق , اقسام مثل IP و-AM تستخدم نظام براهين تفاعلي . ALL هو قسم كل المسائل .
مسائل كاملة[عدل]
Crystal Clear app kdict.png مقالة مفصلة: NP-Complete
فلتكن L \in \mbox{NP} نقول أنَّ L مسألة \mbox{NP} كاملة اذا تحقق :
لكل L' \in \mbox{NP} يتحقق : L' \le _p L
نسمي \mbox{NP-complete} قسم اللغات التي هي NP كاملة. بشكل مشابه يمكن تعريف مسائل كاملة في كل قسم لغات مثل : \mbox{P,PSPACE},... .
إنَّ المسائل الكاملة تُعتبر "مسائل صعبة" بمفهوم انه لو وُجد حل بوقت حدودي لاحداها هذا يعني أنَّ كل المسائل في \mbox{ NP} يمكن حلها بوقت حدودي . النظرية التالية تشرح هذا الامر :
\mbox{NP-complete} \cap \mbox{P} \ne \emptyset اذا وفقط اذا \mbox{NP} = \mbox{P} .
مبرهنة كوك وليفين[عدل]
Crystal Clear app kdict.png مقالة مفصلة: مبرهنة كوك وليفين
الاكتفاء (مسماة بالإنجليزية SAT) مسألة NP كاملة. وقد كانت هذه اول لغة يُبرهن انها NP كاملة . واهميتها كانت بانها الشرارة التي اوقدت نظرية التعقيد الحسابي والسعي وراء النماذج الحسابية المختلفة , بعد أن تم برهنة أنَّ مسألة الاكتفاء هي NP كاملة تبين أنَّ الالاف المسائل هي أيضا كذلك .
ولعل اهم المسائل كاملة هي :
مسألة الاكتفاء (SAT)
مشكلة تلوين المخطط.
مشكلة المخطط الكامل ضمن مخطط.
مشكلة الرحالة التاجر.
مسار هاملتونياني
مبرهنات الهرمية[عدل]
هذه المبرهنات تعتبر نتائج اساسية التي بواسطتها يمكن فصل اقسام التعقيد , والحدس خلف هذه المبرهنات هو أنك اذا كان عندك موارد اكثر باستطاعتك ان تفعل اكثر , ولهذه المبرهنات عدة نصوص اذ أنَّه لكل مورد ومقياس تعقيد يوجد نص خاص به ونُدرج بعض هذه :
اذا كانت (f(n يمكن حسابها بوقت ((O(f(n حيث أنَّ (log(n)<f(n حينها : \mbox{DTIME(f(n))} \subsetneq \mbox{DTIME(f(n)log(f(n)))}
فلتكن (s(n و- (g(n دالتين يمكن حسابهما بواسطة ((O(s(n و- ((O(g(n مكان حينها واذا : (o(g(n))=s(n , حينها : \mbox{SPACE(s(n))} \subsetneq \mbox{SPACE(g(n))}
ونتيجة لهذه المبرهنات فاننا نحصل على : \mbox{P} \ne \mbox{EXP} وكذلك : \mbox{NP} \ne \mbox{NEXP} وكذلك : \mbox{L} \ne \mbox{PSPACE} , كما أن هذه المبرهنات بشكل ما تناقض اطروحة ادموندز- كوبهام اذ انه هذا يعني أنَّ هنالك مسائل لا يمكن حلها بوقت اقل من \mbox{n}^{1000} وبشكل واضح هذا الوقت يُعتبر غير واقعي وغير قابل للوصول حتى بالنسبة ل- n=2 !
الاختصار[عدل]
الاختصار(reduction) هو وسيلة لنقل مسألة إلى مسألة اخرى بحيث انه يمكن الاستعانة بحل المسألة الثانية لحل المسألة الاولى . وقد شاع استخدام هذه الاختصارات في الحياة اليومية , مثال واضح على هذا هو لنفرض اننا نريد ان نجد شارع في مدينة مُعينة لعل هذا يكون اسهل لو كان معنا خريطة اذا فاننا اذا استخدمنا الخريطة نكون بهذا قد اختصرنا مسألة ايجاد الشارع في المدينة لايجاد الشارع في الخريطة والتي حتما ستكون اسهل . وبالعادة في الاختصارات عندنا مسألتين A و- B اذا فرضنا أنَّ B يمكن اختصارها ل-A حينها حل المسألة A يمكن الاستعانة به لحل المسألة B , ولننظر إلى المسائل التالية :
السفر من اسطنبول إلى مكة
شراء تذكرة طيران من اسطنبول إلى مكة
جمع النقود لشراء التذكرة من اسطنبول إلى مكة
ايجاد عمل لتحصيل النقود
يمكن رؤية ان كل واحدة من المسائل يمكن اختصارها للاخرى بالشكل التالي : اذا حللنا مسألة ايجاد عمل حينها يمكن جمع النقود لشراء التذكرة من اسطنبول إلى مكة في الوقت الذي جمعنا فيه مالا كافيا لشراء التذكرة يمكن حينها شراء التذكرة واخيرا السفر إلى مكة من اسطنبول .
كما ان الاختصارات تظهر كذلك في المسائل الرياضية مثل : قياس مساحة الدائرة يمكن اختصاره لايجاد طول نصف القُطُر , كما انه يمكن اختصار حل هيئة معادلات خطية لعكس مصفوفة. يظهر الاختصار في كثير من المجالات في الرياضيات وذلك لانه بواسطة الاختصارات يمكن تصنيف مسائل الرياضيات اذ انه اذا يمكن اختصار مسألة A للمسألة B حينها المسألة A لا يمكن ان تكون اصعب من المسألة B وهذه النظرة اخذها علوم الحاسوب لتصنيف الخوارزميات وقد تمكن علماء الحاسوب بناء نظرية التعقيد الحسابي بواسطة هذه الاداة .
يوجد عدة انواع من الاختصارات ومنها :
اختصارات تيورنج : نقول ان اللغة A \subseteq \{0,1\}^* يمكن اختصارها للغة B\subseteq \{0,1\}^* اذا لكل x\in A عدد خطوات* الحساب هو حدودي بالنسبة لطول المدخل اي Poly(|x|) . * نقصد هنا بالخطوة الحسابية هو اما ان تكون خطوة حسابية بالمفهوم العادي او تكون الخطوة هي الدخول لدالة تحل المسألة B .
اختصارات كارب او قابلية اختصار بواسطة تطبيق حدودي : نقول أَنَّ لغة A \subseteq \{0,1\}^* يمكن اختصارها بوقت حدودي للغة B\subseteq \{0,1\}^* ويُرمز اليه ب- A \le _p B اذا يوجد يوجد دالة يمكن حسابها بوقت حدودي f:\{0,1\}^* \to \{0,1\}^* بحيث انه لكل x\in \{0,1\}^* , x\in A اذا وفقط اذا f(x)\in B
اختصارات ليفين : فليكن f و- g دالتين يمكن حسابهما بوقت حدودي , حينها يمكن تسميتهما اختصار ليفين من اللغة R للغة 'R اذا كانت f اختصار كارب من S_R =\{x:\exists y , (x,y)\in R \} للغة S_R' =\{x:\exists y , (x,y)\in R' \} ولكل x\in S_R وكذلك y'\in R'(f(x)) حينها (x,g(x,y'))\in R في حين أنَّ R'(x')=\{y':(x',y')\in R'\} .
اختصارات سعة مواردها لوجارثمية : نبدأ اولا بتعريف نوع خاص من الدوال والتي هي يمكن حسابها بسعة موارد لوجارثمية :
فلتكن f: \{0,1\}^* \to \{0,1\}^* دالة محدودة حدوديا بمعنى انه يوجد ثابت c>0 بحيث أَنَّ f(x) \le |x|^c . ونقول أَنَّ f يمكن حسابها بسعة موارد لوجارثمية اذا يمكن حساب اللغتين L_f=\{\langle x,i \rangle | f(x)_i =1 \} وكذلك L'_f=\{\langle x,i \rangle | i \le |f(x)| \} يمكن حسابها بسعة موارد لوجارثمية.
والان نعرف اختصارات سعة مواردها لوجارثمية بالشكل التالي : نقول أَنَّ لغة A \subseteq \{0,1\}^* يمكن اختصارها بسعة موارد حدودية للغة B\subseteq \{0,1\}^* ويُرمز اليه ب- A \le _l B اذا اذا يوجد يوجد دالة يمكن حسابها بسعة موارد لوجارثمية f:\{0,1\}^* \to \{0,1\}^* بحيث انه لكل x\in \{0,1\}^* , x\in A اذا وفقط اذا f(x)\in B
مسائل غير محلولة[عدل]
ظهرت مسائل في نظرية التعقيد ولعلها من اهم المسائل في الالفية , حيث ان تطور العلوم بشكل عام سيكون اسرع لو كان لها حل . اهم هذه المسائل هي :
مسألة NP-P[عدل]
من السهل ملاحظة أن المسائل الحتمية الحدودية (P) هي ضمن المسائل غير حتمية حدودية (NP), لكن المسألة المقابلة والتي تسأل هل مجموعة المسائل غير حتمية مجموعة جزئية لمجموعة المسائل الحتمية ؟ ولم يتمكن من الجواب عنها علماء المعلوميات منذ سنة 1971 إلى الآن هو هل هناك تساو أو اختلاف بين المجموعتين ؟ وقد عُرض عام 2000 مكافئة قدرها مليون دولار لمن يحل المسألة وذلك بواسطة معهد كلاي .
تلقي هذه المسألة بظلها على كل مجالات العلوم الحديثة ولحل هذه المسألة اهمية بالغة على تطور مجال علم التشفير او انتكاسه حيث انه لو NP=P حينها علم التشفير الحديث لن يكون له اي اهمية من الناحية النظرية ! ولكن لو تحقق هذا فان مجال تصميم الشرائح الالكترونية , تحليل الصور الرقمية , الذكاء الصناعي ... وغيرها من المجالات ستتطور لتكون في اقصى تطورها .
مسائل التي لا تتبع P ولا تتبع NP كاملة[عدل]
لقد بيَّن لاندر انه في حال انه \mbox{P}\ne \mbox{NP} حينها يوجد مسائل التي لا تتبع P ولا تتبع NP كاملة , للان لم يبرهن احد على وجود مثل هذه المسائل ولكن هنالك حدسيات عن بعض المسائل التي محتمل جدا ان تكون كذلك منها : تحليل لعوامل , تطابق المخططات
