إدارة الموسوعة 1: -

2012-08-30T15:54:30Z

→ مراجعة أقدم		مراجعة 15:54، 30 أغسطس 2012
سطر 95:		سطر 95:
	[[تصنيف:معلوماتية]]		[[تصنيف:معلوماتية]]
	[[تصنيف:مسائل NP كاملة]]		[[تصنيف:مسائل NP كاملة]]

	~~[[ca:NP-complet]]~~
	~~[[cs:NP-úplnost]]~~
	~~[[da:NP-komplet]]~~
	~~[[de:NP-Vollständigkeit]]~~
	~~[[en:NP-complete]]~~
	~~[[es:NP-completo]]~~
	~~[[fa:ان‌پی کامل]]~~
	~~[[fi:NP-täydellisyys]]~~
	~~[[fr:Problème NP-complet]]~~
	~~[[it:NP-Completo]]~~
	~~[[ja:NP完全問題]]~~
	~~[[ko:NP-완전]]~~
	~~[[nl:NP-volledig]]~~
	~~[[nn:NP-komplett]]~~
	~~[[no:NP-komplett]]~~
	~~[[pl:Problem NP-zupełny]]~~
	~~[[pt:NP-completo]]~~
	~~[[ru:NP-полная задача]]~~
	~~[[simple:NP-complete]]~~
	~~[[sk:NP-úplný problém]]~~
	~~[[sr:НП-комплетни проблеми]]~~
	~~[[sv:NP-fullständig]]~~
	~~[[th:เอ็นพีบริบูรณ์]]~~
	~~[[uk:NP-повна задача]]~~
	~~[[zh:NP完全]]~~

WikiSysop: ١ مراجعة: الصفحات في تصنيف رياضيات

2010-11-12T21:15:55Z

١ مراجعة: الصفحات في تصنيف رياضيات

صفحة جديدة

{{مسألة NP كاملة}}
في الرياضيات صنف [[نظرية التعقيد|التعقيد]]، تُعرف المسائل NP الكاملة، بأنها كل ما يحقق الشرطين الآتيين:

* كل مسألة من صنف NP، تختصر لمسألة واحدة A.
* المسألة A من صنف NP.

لتحديد وجودية المسائل NP الكاملة، قام كوك وكيفين باستعمال [[آلة تورينغ]] للبرهنة على وجود مسألة NP الكاملة، وهي صيغة قيم ثنائية مكونة من عطف عدة صيغ كل صيغة هي مجموعة فصل عدة متغيرات ثنائية أي لها 1 أو 0 كقيمة.

== مبرهنة كوك وليفين ==
نص المبرهنة هو: SAT مشكل حدودي غير محدد كامل (NP-compet).

تنسب في الأغلب لكوك، حيث أن ليفين وجد نفس النتائج دون أن يكون على علم بنتائج كوك، ففي ذلك الوقت لم تكن هناك وسائل اتصال متطورة (ما بين 1971 و 1974).
=== مفهوم الإختصار ===
نقول أن <math>L_1</math> يتم اختصاره إلى <math>L_2</math> في وقت حدودي، في حالة وجود دالة قابلة للحساب في وقت حدودي، <math>f : \left\{0,1\right\}^* \rightarrow \left\{0,1\right\}^*</math> يحيث لكل <math>x \in \left\{0,1\right\}^*</math>, <math>x \in L_1</math> إذا وفقط إذا كان <math>f(x) \in L_2</math>. نسمي الدالة <math>f\!</math> '''دالة الإختصار''', وخوارزمية حدودية التي تحسب <math>f\!</math> يسمى '''
خوارزمية الإختصار'''.

=== البرهنة ===
نقدم هنا برهنة تقريبية.

A مسألة من صنف NP. هذه المسألة مقبولة من [[آلة تورينغ]] M غير محددة. بالنسبة لكل مداخلة w ل M، توجد صيغة <math>\varphi_w </math> ذات بعد حدودي بالنسبة لبعد w والتي تكون كافية إذا وفقط إذا كانت w مقبولة من M.

نرمز ل <math>n=|w|</math> بعد w. بما أن الآلة M تعمل في وقت حدودي، يوجد عدد طبيعي ثابت k حيث كل عملية حسابية على w تكون على الأكثر بطول <math>n^k </math>. نضيف سلسلة انتظار مغلقة، ونفترض أن طول العمليات هو بالضبط <math>n^k </math>. آلة تورينغ تستعمل <math>n^k </math> خلية. الإعدادات الخاصة بحساب مقبول يكون أيضا بطول <math>n^k </math>. عند كتابة جميع الإعدادات الواحدة تحت الأخرى، تحصل على جدول. ونحصل على الصيغة <math>\varphi_w </math> التي ترمز لوجود جدول رموز محصل عن طريق الإعدادات المتتابعة لحساب مقبول ل w.

{| border="1"
! إعدادات !! 0 !! 1 !! 2 !! 3 !!... !! n^k
|-
| <math>C_0 = </math>|| <math>q_0</math> || <math>W_1</math> || <math>W_2</math> || <math>W_3</math> ||... || #
|-
| <math>C_1 = </math>|| <math>W'_1</math> || <math>q_1</math> || <math>W_2</math> || <math>W_3</math> ||... || #
|-
| <math>C_2 =</math> || <math>W'_1</math> || <math>W'_2</math> || <math>q_2</math> || <math>W_3</math> ||... || #
|-
| <math>C_3 = </math>||... ||... ||... ||... ||... || #
|-
|... ||... ||... ||... ||... ||... || #
|-
| <math>C_{n^k}</math> ||... ||... ||... ||... ||... ||...
|}

بالنسبة لكل خانة <math>(i,j) \,</math> من الجدول مع <math>0 \ge i</math> و<math>j \le n^k</math>.و كل رمز <math>a \,</math>، ندخل المتغير <math>X_{i,j,a} \,</math> الذي يرمز لكون الخانة تتضمن أو لا الرمز <math>a \,</math>. عدد هذه المتغيرات حدودي.

عندنا العلاقة: <math>\varphi_w = \varphi_{cell} \wedge \varphi_{start} \wedge \varphi_{move} \wedge \varphi_{accept}</math> حيث كل من <math>\varphi_{cell}</math> و<math>\varphi_{start}</math> و<math>\varphi_{move}</math> و<math>\varphi_{accept}</math> ترمز لوجود مسار مقبول.
==== الحصول على الصيغة <math>\varphi_{cell}</math> ====
الصيغة <math>\varphi_{cell} \,</math> هي صيغة عطف لكل خانة (i,j). وهي تضمن على الأقل أن متغير <math>X_{i,j,a} \,</math> له القيمة 1 لكن متغيران <math>X_{i,j,a} \,</math> و<math>X_{i,j,b} \,</math> لكل <math>a \ne b \,</math> لا يمكن أن يكون لهما القيمة 1 في نفس الوقت.

الصيغة تكتب على الشكل:
<math>\varphi_{cell} = \wedge_{0\le i,j\le n^k} \left[ (\vee_{a\in A} X_{i,j,a}) \wedge (\wedge_{a \ne b} \lnot(X_{i,j,a} \wedge X_{i,j,b})) \right]</math>

==== الحصول على الصيغة <math>\varphi_{start}</math> ====
تكتب الصيغة هكذا:
<math>x_{0,0,q_0}\wedge x_{0,1,w_1}\wedge x_{0,2,w_2}\wedge...\wedge x_{0,n,w_n}\wedge x_{0,n+1,D}\wedge...\wedge x_{0,n^k,D}</math>

مع ملاحظة أن D يرمز ل #.

==== الحصول على الصيغة <math>\varphi_{accept}</math> ====
هذه الصيغة تضمن على الأقل أن أحد خانات السطر الأخير من الجدول يضم حالة نهائية.

الصيغة تكتب على الشكل:
<math>\varphi_{accept} = \lor_{0\le j\le n^k} \;and\; {q\in F}\; ^x\!n^k,j,q </math>

==== الحصول على الصيغة <math>\varphi_{move}</math> ====
== لائحة ب 21 مسألة NP كلاسيكية (كارب) ==
[[ملف:Relative NPC chart.png|تصغير|المسائل الكلاسيكية]]
* SATISFIABILITY : الإكتفاء، إيجاد قيم لمتغيرات ثنائية تجعل الصيغة العادية لعطف صحيحة.
* CLIQUE : الزمرة، إيجاد زمرة أي مخطط كامل ذو بعد محدد ضمن مخطط آخر.
* SET PACKING :
* VERTEX COVER : إيجاد ضمن مخطط مجموعة ارتباطات تتصل بكل القمم.
* SET COVERING :
* FEEDBACK ARC SET :
* FEEDBACK NODE SET :
* DIRECTED HAMILTONIAN CIRCUIT : البحث عن [[مسار هاملتونياني]] مغلق
* UNDIRECTED HAMILTONIAN CIRCUIT : البحث عن [[مسار هاملتونياني]] مفتوح
* 0-1 INTEGER PROGRAMMING :
* 3-SAT : إيجاد قيم لمتغيرات ثنائية تجعل الصيغة العادية لعطف صحيحة تضم كل مجموعة 3 عناصر.
* CHROMATIC NUMBER : تحديد أصغر عدد تلوين مخطط حيث كل قمتين مرتبطتين يكون لهما لونان مختلفان.
* CLIQUE COVER :
* EXACT COVER :
* MATCHING à 3 dimensions :
* STEINER TREE :
* HITTING SET :
* KNAPSACK :
* JOB SEQUENCING :
* PARTITION :
* MAX-CUT :

== أنظر أيضا ==
* [[نظرية التعقيد الحسابي]].
* [[مسألة P=NP]]
* [[إن بي]]

{{بوابة رياضيات}}

[[تصنيف:رياضيات]]
[[تصنيف:تعقيد]]
[[تصنيف:معلوماتية]]
[[تصنيف:مسائل NP كاملة]]

[[ca:NP-complet]]
[[cs:NP-úplnost]]
[[da:NP-komplet]]
[[de:NP-Vollständigkeit]]
[[en:NP-complete]]
[[es:NP-completo]]
[[fa:ان‌پی کامل]]
[[fi:NP-täydellisyys]]
[[fr:Problème NP-complet]]
[[it:NP-Completo]]
[[ja:NP完全問題]]
[[ko:NP-완전]]
[[nl:NP-volledig]]
[[nn:NP-komplett]]
[[no:NP-komplett]]
[[pl:Problem NP-zupełny]]
[[pt:NP-completo]]
[[ru:NP-полная задача]]
[[simple:NP-complete]]
[[sk:NP-úplný problém]]
[[sr:НП-комплетни проблеми]]
[[sv:NP-fullständig]]
[[th:เอ็นพีบริบูรณ์]]
[[uk:NP-повна задача]]
[[zh:NP完全]]

مسألة NP كاملة - تاريخ المراجعة

إدارة الموسوعة 1: -

WikiSysop: ١ مراجعة: الصفحات في تصنيف رياضيات