Loading AI tools
من ويكيبيديا، الموسوعة الحرة
هي قسم(class) لغات، اللغة(language) في سياقنا هذا هي مجموعة سلاسل (strings) من رموز الابجدية (alphabet) ومسألة التقرير (Decision problem) هي باعطانا سلسلة(string) من الرموز هل هي موجودة باللغة ام لا أي: ، ويوجد خوارزمية A بحيث ان A(s)=1 فقط إذا . واللغات التي في NP هي التي يمكن حلها (أي حل مسألة التقرير) بواسطة آلة تيورنغ غير حتمية متعددة الحدود، ولعل هذا القسم من اللغات هو الأهم في نظرية التعقيد الحسابي إذ ان اللغات التي يحتويها تمتد إلى كل فروع علم الحاسوب والنتائج على هذا قسم NP يؤثر في كل علوم الحاسوب. الاسم NP هو اختصار ل- Non deterministic Polynomial time
في بداية الستينات من القرن العشرين، حاول العالم Karp حل مسألة التقرير لمسألة البائع المتجول وهذا كان بادئ الامر وبعد وقت قصير Rabin اسس نظرية التعقيد ووضع حجارة الاساس لها وكلمة التعقيد(complexity) ظهرت فقط في عام 1965 وبعدها تم تعريف متى تكون الخوارزمية «جيدة» وتم هذا بواسطة Edmonds، اما cook فقد عرف NP وP وكذلك عرف مسائل NP كاملة وبين ان SAT هي كذلك واظهر ان كل مسألة NP كاملة يمكن حلها بواسطة SAT وذلك يتم بواسطة دالة تحويل (reduction) وقد عرف Karp لاحقا مسائل NP كاملة منها TSP وعرفت هذه المسائل بقائمة karp ال-21 وفي عام 2000 تم رصد جائزة بمبلغ مليون دولار لمن يحل مسألة NP=P.
يوجد عدة تعريفات ل-NP ولعل اهمها هو التالي:
إذا كان و بحيث ان 1=(M(x,u حينها نسمي u اثبات أو برهان(certificate) ل-x ونسمي M آلة فاحصة(verifier)(لانها تفحص إذا كان x في L بواسطة برهان u).
تعريف NTIME: لكل دالة و- بحيث ان إذا يوجد ثابت c>0 وأيضا يوجد NDTM cT(n)-time (آلة تيورنج غير حتمية) M بحيث: .[1][2]
حينها نعرف NP بالشكل التالي: وهذا التعريف هو أول تعريف ل-NP.
في بداية التسعينات برهنت هذه النظرية لتفتح افق جديدة في علوم الحاسوب ونظرية PCP هي نظرية اساسية في علم التعقيد إذ انه بواسطة هذا التعريف باتت صورة المسائل التي هي NP كاملة التي يمكن اعطائها حل مقرب اوضح حيث نتج عن هذه النظرية الكثير من النتائج عن صعوبة تقريب حل مسائل NP كاملة.
تقريبا كل المسائل العملية موجودة في هذا القسم ولكن في حال ان حينها لا يوجد لاي من هذه المسائل خوارزمية جيدة بمعنى انه لا توجد آلة تيورنج حتمية بوقت حدودي تقرر هذه اللغات.
مسألة تقرير S في RP إذا يوجد خوارزمية احتمالية بوقت حدودي A بحيث ان الاحتمال بأن الخوارزمية A تقرر x بشكل صحيح أكبر من أي: ، ولكل الخوارزمية لا تخطأ في تقرير x أي: RP هو اختصار Randomized Polynomial time وهذا القسم يعتبر من الاقسام العملية وذلك بالرغم من عدم معرفة إذا ما RP=P حيث انه يمكن كتابة برامج احتمالية وهذا يمكننا من استخدام اللغات فيه، أحد أهم اللغات التي فيه والتي لا يعرف لها خوارزمية حتمية بوقت حدودي هي مسألة فحص إذا ما متعددا الحدود متساويين.
هاتان اللغتان هما NP كاملتين كذلك.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.