Movatterモバイル変換


[0]ホーム

URL:


انتقل إلى المحتوى
ويكيبيديا
بحث

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

من ويكيبيديا، الموسوعة الحرة
(بالتحويل منUP)

في علم التعقيد الحسابي القسم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{\displaystyle 0<b<p} , وعددcN{\displaystyle c\in \mathbb {N} }

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

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

كربتوغرافي

[عدل]

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

انظر أيضا

[عدل]
أقسام التعقيد المهمة
ممكنة للتنفيذ
مشكوك في إمكانية تنفيذها
غير قابل للتنفيذ
أقسام هرمية
عائلات اقسام
مجلوبة من «https://ar.wikipedia.org/w/index.php?title=يو_بي_(تعقيد_حسابي)&oldid=68075119»
تصنيفان:
تصنيفات مخفية:

[8]ページ先頭

©2009-2025 Movatter.jp