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

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

في علم التعقيد الحسابي القسم UP هو قسم كل المسائل التي يمكن تقريرها بوقت كثير الحدود على الة تيورنج ليست حتمية بحيث أنَّه يوجد على الاكثر مسار حساب واحد اجابته "نعم" . هذا القسم يحوي P ويحتويه القسم NP .

تعريف[عدل]

  • الة تيورنج جَلِيَّة (Unambiguous turing machine) هي الة تيورنج ليست حتمية (nondetreminstic turing machine) بحيث انه لكل مُدخل يوجد مسار حساب واحد على الاكثر الذي يقبل المُدخل . و- UP هي مجموعة المسائل التي يمكن تقريرها بواسطة الة تيورنج جلية .
  • مسألة L تابعة ل-UP اذا يوجد الة تيورنج حتمية وقتها كثير الحدود M وعدد ثابت c بحيث أنَّ :
x تابع للمسألة اذا يوجد تصديق وحيد (y (unique certificate عندما (y|=O(|x|c| بحيث يتحقق M(x,y)=1 .
x ليس تابعا للمسألة اذا لا يوجد تصديق وحيد y عندما (y|=O(|x|c| بحيث يتحقق M(x,y)=1 .

امثلة[عدل]

هناك عدة مسائل غير معلوم اذا ما هي في P وهي موجودة في UP احد الامثلة المهمة هي مسألة اللوغاريتم المتقطع (discrete log) وهي المسألة التالية :

مُدخل : عدد أولي p , جذر أولي a mod p وعدد صحيح b بحيث ان  0 < b < p , وعدد c\in\mathbb{N}

مُخرج : هل يوجد عدد L بحيث 1\le L \le c بحيث  a^L\equiv b(mod \ p)

امثلة اخرى من ضمنها تحليل لعوامل , ...

كربتوغرافي[عدل]

لعل وجود مسائل في  \mbox{UP}  \setminus \mbox{P} له اهمية عظمى في علم التشفير الحديث , حيث أنَّ وجود دوال وحيدة الاتجاه يعتمد بشدة على الفرضية  P \ne UP , وتعتبر مسألة اللوغاريتم المتقطع احد اهم المسائل التي يُفترض انها وحيدة الاتجاه , ولكن لا احد برهن ان المسألة كذلك ولكن علم التشفير الحديث يعتمد بشدة على هذه الفرضية وحاليا تُعد المسألة صعبة لانه لم يتم ايجاد خوارزمية سريعة لحل المسالة . برهنة وجود دوال وحيدة الاتجاه يعني هذا بالضرورة أنَّ P\ne NP , لقد بُرهن أن دوال وحيدة الاتجاه موجودة اذا وفقط اذا UP\ne P .

مسائل كاملة[عدل]

لا يُعرف اذا ما يوجد مسائل كاملة ل- UP , ولعله لا يوجد مسائل كهذه لانه يوجد اوراكل (موحي او oracle) بحيث انه لا يوجد مسائل كاملة [1][2] .

مصادر[عدل]

  1. ^ Hartmanis J., L. Hemachandra ,Complexity classes without machines: On complete languages for UP , Theoret. Comput. Sci. 58(1988) 129-142.
  2. ^ Hemachandra ,L.A., Structure of complixety classes : seperation,collapse,and completeness,in:Mathematical Foundation of computer science,lecture notes in computer science,Vol. 324 (Springer ,Berlin,1988) 59-73.

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