شعار
يونيونبيديا
الاتصالات
'احصل عليه من Google Play    
الجديد! تحميل يونيونبيديا على جهاز الروبوت الخاص بك!
تحميل
وصول أسرع من المتصفح!
 

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

اختصارات: الخلافات، أوجه التشابه، التشابه معامل، المراجع.

الفرق بين ZPP (تعقيد حسابي) وقسم تعقيد

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

في نظرية التعقيد الحسابي القسمهو قسمكل المسائل التي يمكن تقريرها بواسطة آلة تيورنج احتمالية بوقت حدودي مع إمكانية الفشل في الاتيان بجواب، أيضا تعريف هذا القسمبأنه قسمكل المسائل التي يمكن تقريرها بواسطة آلة تيورنج احتمالية التي لا تخطئ أبدًا بحيث أن وقتها المتوقع (expected running time) هو حدودي أي أي لو أن الخوارزمية ترمي قطع نقدية عشوائية خلال وقت عملها فإنَّ جوابها صحيح دائما ولكن معدل وقت عملها لكل مُدخل طوله هو (p(n ، حيث أنَّ (p(n هو كثير حدود، القول الاخير يعني انه بشكل عاموقت عمل الخوارزمية هو كثير حدود ولكن يمكن أن يكون هناك مُدخلات بحيث أن وقت عمل الخوارزمية أكثر من حدودي. التعريفان متكافئان. في علمالتعقيد الحسابي، قسمتعقيد هي مجموعة من المسائل المُتعلقة بالاساس فيما بينها بمورد مُعين، اغلب الاقساملديها التعريف التالي: على سبيل المثال: القسمNP هو مجموعة المسائل التي يمكن حلها بوقت حدودي (أي O(n^c)) بواسطة آلة تيورنج غير حتمية، مثال آخر هو القسمبيسبايس وهو مجموعة المسائل التي يمكن حلها بواسطة آلة تيورنج حتمية وتستخدممكان اضافي طوله حدودي (أي انها تسخدمO(n^c) مكان اضافي).

أوجه التشابه بين ZPP (تعقيد حسابي) وقسم تعقيد

ZPP (تعقيد حسابي) وقسم تعقيد يكون 4 الأشياء المشتركة (في يونيونبيديا): BPP، نظرية التعقيد الحسابي، مسألة كثير حدود وكثير حدود غير قطعي، خوارزمية.

BPP

في علمالتعقيد الحسابي قسمالتعقيد هو قسمالمسائل التي يوجد آلة تيورنج احتمالية وقتها كثير حدود بحيث أن احتمال الخطأ على الأكثر 1/3 لكل المُدخلات.

BPP وZPP (تعقيد حسابي) · BPP وقسم تعقيد · شاهد المزيد »

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

نظرية التعقيد هي فرع من فروع نظرية الحوسبة والرياضيات، وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وربط أقسامالتعقيد complexity classes ببعضها، والمسألة الحاسوبية هي المسألة التي يستطيع الحاسوب بحلها.

ZPP (تعقيد حسابي) ونظرية التعقيد الحسابي · قسم تعقيد ونظرية التعقيد الحسابي · شاهد المزيد »

مسألة كثير حدود وكثير حدود غير قطعي

يسار إن العلاقة بين مسائل التعقيد كثيرة الحدود وكثير حدود غير قطعي هي مسألة غير محلولة في المعلوماتية النظرية.

ZPP (تعقيد حسابي) ومسألة كثير حدود وكثير حدود غير قطعي · قسم تعقيد ومسألة كثير حدود وكثير حدود غير قطعي · شاهد المزيد »

خوارزمية

يسار الخوارزمية هي مجموعة من الخطوات الرياضية والمنطقية والمتسلسلة اللازمة لحل مشكلة ما.

ZPP (تعقيد حسابي) وخوارزمية · خوارزمية وقسم تعقيد · شاهد المزيد »

القائمة أعلاه يجيب على الأسئلة التالية

المقارنة بين ZPP (تعقيد حسابي) وقسم تعقيد

ZPP (تعقيد حسابي) له 5 العلاقات، في حين قسم تعقيد ديه 6. كما لديهم في شيوعا 4، مؤشر التشابه هو 36.36% = 4 / (5 + 6).

المراجع

يوضح هذا المقال العلاقة بين ZPP (تعقيد حسابي) وقسم تعقيد. للوصول إلى كل مادة من المواد التي تم استخراج المعلومات، يرجى زيارة الموقع التالي:

مرحبا! نحن في الفيسبوك الآن! »