ZPP (تعقيد حسابي)

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

في نظرية التعقيد الحسابي القسم ZPP هو قسم كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج احتمالية بوقت حدودي مع امكانية الفشل في الاتيان بجواب ,أيضا تعريف هذا القسم بأنه قسم كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج احتمالية التي لا تخطأ ابدا بحيث أن وقتها المتوقع(expected running time) هو حدودي اي أي لو أن الخوارزمية ترمي قطع نقدية عشوائية خلال وقت عملها فإنَّ جوابها صحيح دائما ولكن معدل وقت عملها لكل مُدخل طوله هو (p(n , حيث أنَّ (p(n هو كثير حدود , القول الاخير يعني انه بشكل عام وقت عمل الخوارزمية هو كثير حدود ولكن يمكن ان يكون هناك مُدخلات بحيث ان وقت عمل الخوارزمية أكثر من حدودي . التعريفان متكافئان .

تعريف[عدل]

  • القسم \mbox{ZTIME(T(n))} يحوي كل المسائل او اللغات ,L, والتي يوجد آلة تيورنج احتمالية حيث أن وقتها المُتوقع هو O(T(n)) وهذه الالة لا تخطئ أي :
  •  \mbox{x} \in \mbox{L}\Rightarrow  \mbox{Pr}[\mbox{M(x)=1}]=1
  •  \mbox{x} \notin \mbox{L}\Rightarrow  \mbox{Pr}[\mbox{M(x)=0}]=1
نعرف \mbox{ZPP}=\cup _{c \ge 0 } \mbox{ZTIME}(n^c)
  •  \mbox{L} \in \mbox{ZPP} اذا يوجد آلة تيورنج احتمالية كثيرة الحدود,A, بحيث أنه لكل  x\in \{0,1\}^*  :
  •  \mbox{Pr}[A(x)\in \{\chi_L(x),\bot\}]=1
  •  \mbox{Pr}[A(x)\in \chi_L(x)]\ge \frac12
بحيث أن :
  •  \chi_L(x)=1 \iff x \in L
  •  \chi_L(x)=0 \iff x \notin L
والرمز \bot معناه ان الخوارزمية لم تنجح في الاتيان باجابة صحيحة .
  • تعريف اخر هو :  \mbox{ZPP} = \mbox{RP} \cap \mbox{co-RP} اي انَّ ZPP هو قسم المسائل التي يوجد لها آلة تيورنج احتمالية بحيث أنَّ احتمال ان تخطأ الالة على مُدخلات تابعة للمسألة ( اي جوابها الصحيح "نعم") هو على الأكثر 1/2 وكذلك يوجد آلة اخرى تحل مسألة التقرير لهذه المسألة وتخطأ على مُدخلات ليست تابعة للمسألة ( اي جوابها الصحيح "لا") باحتمال على الأكثر 1/2 .

علاقتها باقسام اخرى[عدل]

  • ZPP يحوي P وذلك لان لكل مسألة في القسم P يمكن محاكاة الالة الحتمية التي تحل مسألة القرار بواسطة آلة تيورنج احتمالية .
  • ZPP مَحوي ب- BPP وذلك لان  \mbox{ZPP} = \mbox{co-RP} \cap \mbox{RP} \subseteq \mbox{BPP} .
  • ZPP مَحوي ب-  \mbox{NP} \cap \mbox{co-NP} .

حدسيات[عدل]

كما هو معلوم لعل حل حدسية NP-P هي الأشهر ولكن هنالك عدة حدسيات لم تُحل مثل :

  • هل ZPP=NP ? اذا كان الجواب "لا" حينها NP لا يساوي P . خلاف هذا تظل مسألة NP مقابل P حدسية .
  • هل ZPP=BPP=EXP ? اذا كان الجواب "نعم" حينها P لا يساوي NP خلاف هذا المسألة NP مقابل P تظل حدسية
  • هل ZPP=P ? وهذا السؤال أيضا ما زال حدسية ولكن العلماء يظنون ان الجواب نعم وعلى خلاف الاسئلة التي طرحت آنفا فان الاجابة عن السؤال هذا قد لا تُحدث تطورا في العلاقة بين NP و- P .

انظر أيضا[عدل]