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

• آلة تيورنج جَلِيَّة (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 بحيث ان ${\displaystyle 0<b<p}$ , وعدد ${\displaystyle c\in \mathbb {N} }$

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

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

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

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

• قسم تعقيد
• نظرية التعقيد الحسابي.
• مسألة P=NP
• خوارزمية

• بوابة علم الحاسوب
• بوابة رياضيات