مرجع
آخر الزيارات

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

309 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: في علم التعقيد الحسابي القسم هو قسم كل المسائل التي يمكن تقريرها بوقت كثير الحدود على آلة تيورنج ليست حتمية بحيث أنَّه يوجد على الأكثر مسار حساب واحد اجابته «نعم». في هذه المقالة 6 أقسام: «تعريف»، «مُخرج: هل يوجد عدد L بحيث بحيث» و«مسائل كاملة» وغيرها.
المحتويات
  1. تعريف
  2. مُخرج: هل يوجد عدد L بحيث بحيث
  3. مسائل كاملة
  4. امثلة
  5. كربتوغرافي
  6. قسم تعقيد

تعريفًا بالموضوع، في علم التعقيد الحسابي القسم هو قسم كل المسائل التي يمكن تقريرها بوقت كثير الحدود على آلة تيورنج ليست حتمية بحيث أنَّه يوجد على الأكثر مسار حساب واحد اجابته «نعم». هذا القسم يحوي P ويحتويه القسم NP . وتعرض الأقسام التالية جوانب أخرى من الموضوع.

تعريف

وفي هذا السياق، آلة تيورنج جَلِيَّة (Unambiguous turing machine) هي آلة تيورنج ليست حتمية (nondetreminstic turing machine) بحيث انه لكل مُدخل يوجد مسار حساب واحد على الأكثر الذي يقبل المُدخل. و- UP هي مجموعة المسائل التي يمكن تقريرها بواسطة آلة تيورنج جلية.

وفي السياق ذاته، مسألة L تابعة ل-UP إذا يوجد آلة تيورنج حتمية وقتها كثير الحدود M وعدد ثابت c بحيث أنَّ:

مُخرج: هل يوجد عدد L بحيث بحيث

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

مسائل كاملة

انظر كذلك

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

مصادر

امثلة

وفي هذا الصدد، مُدخل: عدد أولي p , جذر أولي a mod p وعدد صحيح b بحيث ان , وعدد

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

كربتوغرافي

كذلك، لعل وجود مسائل في له اهمية عظمى في علم التشفير الحديث، حيث أنَّ وجود دوال وحيدة الاتجاه يعتمد بشدة على الفرضية , وتعتبر مسألة اللوغاريتم المتقطع أحد أهم المسائل التي يُفترض انها وحيدة الاتجاه، ولكن لا أحد برهن ان المسألة كذلك ولكن علم التشفير الحديث يعتمد بشدة على هذه الفرضية وفي الوقت الحالي تُعد المسألة صعبة لانه لم يتم ايجاد خوارزمية سريعة لحل المسالة. برهنة وجود دوال وحيدة الاتجاه يعني هذا بالضرورة أنَّ , لقد بُرهن أن دوال وحيدة الاتجاه موجودة إذا وفقط إذا .

قسم تعقيد

مسألة P=NP

نظرية التعقيد الحسابي.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.