تعقيد الحالة المتوسطة

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

توجد ثلاثة دوافع رئيسية لدراسة تعقيد الحالة المتوسطة. ^{[ 1 ]} أولًا، على الرغم من أن بعض المشكلات قد تكون مستعصية على الحل في أسوأ الحالات، إلا أن المدخلات التي تُسبب هذا السلوك نادرًا ما تحدث عمليًا، لذا قد يكون تعقيد الحالة المتوسطة مقياسًا أدق لأداء الخوارزمية. ثانيًا، يوفر تحليل تعقيد الحالة المتوسطة أدوات وتقنيات لتوليد حالات صعبة من المشكلات، والتي يمكن استخدامها في مجالات مثل التشفير وإزالة العشوائية . ثالثًا، يسمح تعقيد الحالة المتوسطة بتمييز الخوارزمية الأكثر كفاءة عمليًا من بين الخوارزميات ذات تعقيد الحالة المثلى المكافئ (على سبيل المثال، خوارزمية الفرز السريع ).

يتطلب تحليل الحالة المتوسطة مفهومًا للمدخلات "المتوسطة" للخوارزمية، مما يؤدي إلى مشكلة وضع توزيع احتمالي للمدخلات. بدلاً من ذلك، يمكن استخدام خوارزمية عشوائية . ويؤدي تحليل هذه الخوارزميات إلى المفهوم ذي الصلة بالتعقيد المتوقع . ^{[ 2 ]}^{: 28}

التاريخ والخلفية

دُرست كفاءة الخوارزميات في الحالة المتوسطة منذ تطوير المفاهيم الحديثة للكفاءة الحسابية في خمسينيات القرن الماضي. ركزت معظم هذه الدراسات الأولية على مسائل كانت خوارزميات حلها في أسوأ الحالات ذات زمن متعدد الحدود معروفة بالفعل. ^{[ 3 ]} في عام 1973، نشر دونالد كنوث ^{[ 4 ]} المجلد الثالث من كتاب " فن برمجة الحاسوب" الذي يستعرض بشكل موسع كفاءة الخوارزميات في الحالة المتوسطة للمسائل التي يمكن حلها في أسوأ الحالات ذات زمن متعدد الحدود، مثل الفرز وإيجاد الوسيط.

تُعرَّف الخوارزمية الفعالة لحلّ مسائل $NP$ -complete عمومًا بأنها تلك التي تعمل في زمن متعدد الحدود لجميع المدخلات؛ وهذا يُعادل اشتراط كفاءة عالية في أسوأ الحالات. مع ذلك، قد تكون الخوارزمية غير الفعالة على عدد "صغير" من المدخلات فعالةً مع "معظم" المدخلات التي تظهر في الواقع. لذا، من المستحسن دراسة خصائص هذه الخوارزميات حيث قد يختلف متوسط التعقيد عن أسوأ الحالات، وإيجاد طرق لربط هذين العاملين.

تم تطوير المفاهيم الأساسية لتعقيد الحالة المتوسطة بواسطة ليونيد ليفين في عام 1986 عندما نشر ورقة من صفحة واحدة ^{[ 5 ]} تحدد تعقيد الحالة المتوسطة والاكتمال مع إعطاء مثال على مشكلة كاملة لـ $distNP$ ، وهو نظير الحالة المتوسطة لـ $NP$ .

التعريفات

التعقيد الفعال في الحالة المتوسطة

تتمثل المهمة الأولى في تحديد المقصود بدقة بالخوارزمية الفعالة "في المتوسط". قد يُعرّف أحد المحاولات الأولية الخوارزمية الفعالة في الحالة المتوسطة بأنها تلك التي تعمل في زمن متعدد الحدود متوقع على جميع المدخلات الممكنة. إلا أن هذا التعريف يعاني من عدة عيوب؛ فهو على وجه الخصوص غير متين في مواجهة التغيرات في النموذج الحسابي. على سبيل المثال، لنفترض أن الخوارزمية $A تعمل في زمن tA(x) على المدخل x، وأن الخوارزمية B تعمل في زمن tA(x)$ $²$ على $المدخل x ؛ أي$ أن $B$ $أبطأ$ من $A$ بمقدار $تربيعي . وبشكل بديهي ،$ ينبغي $لأي$ تعريف $لكفاءة$ الحالة $المتوسطة$ أن يُجسّد فكرة أن $A$ فعالة في المتوسط إذا وفقط إذا كانت $B فعالة في المتوسط. مع ذلك، لنفترض أن المدخلات تُسحب عشوائيًا من التوزيع$ $المنتظم$ للسلاسل ذات الطول $n$ ، وأن $A$ تعمل في زمن $n²$ على جميع المدخلات باستثناء السلسلة $n⁻¹$ التي تستغرق $A$ زمنًا $قدره$ $n²$ $.$ عندئذٍ يمكن التحقق بسهولة من أن زمن التشغيل المتوقع لـ $A$ هو متعدد الحدود، بينما زمن التشغيل المتوقع لـ $B$ هو أُسّي. ^[³^]

لإنشاء تعريف أكثر دقة لكفاءة الحالة المتوسطة، من المنطقي السماح للخوارزمية $(أ)$ بالعمل لفترة أطول من زمن متعدد الحدود على بعض المدخلات، ولكن نسبة المدخلات التي تتطلب فيها $(أ)$ زمن تشغيل أطول فأطول تتناقص تدريجيًا. يتجسد هذا المفهوم في الصيغة التالية لمتوسط زمن التشغيل متعدد الحدود، والتي توازن بين زمن التشغيل ونسبة المدخلات:

\Pr _{x\in _{R}D_{n}}\left[t_{A}(x)\geq t\right]\leq {\frac {p(n)}{t^{\epsilon }}}

لكل $n ، t > 0،$ ومتعددة الحدود $p$ ، حيث يمثل $t A (x)$ زمن تشغيل الخوارزمية $A$ على المدخل $x$ ، و $ε$ قيمة ثابتة موجبة. ^{[ 6 ]} ويمكن كتابة ذلك على النحو التالي:

E_{x\in _{R}D_{n}}\left[{\frac {t_{A}(x)^{\epsilon }}{n}}\right]\leq C

لبعض الثوابت $C$ و $ε$ ، حيث $n = | x |$ . ^{[ 7 ]} بعبارة أخرى، تتمتع الخوارزمية $A$ بتعقيد جيد في الحالة المتوسطة إذا تمكنت، بعد تشغيلها لـ $tA$ $($ $n) خطوة ،$ من $حل$ جميع المدخلات باستثناء $جزء$ $⁠nc$ $/$ $(tA (n)) ε من$ المدخلات ذات الطول ⁿ $،$ لبعض $ε و c > 0.$ [ ³^]

مشكلة التوزيع

تتمثل الخطوة التالية في تحديد المدخلات "المتوسطة" لمسألة معينة. ويتحقق ذلك بربط مدخلات كل مسألة بتوزيع احتمالي محدد. أي أن مسألة "الحالة المتوسطة" تتكون من لغة $L$ وتوزيع احتمالي مرتبط بها $D$ ، يشكلان الزوج $(L, D)$ . ^{[ 7 ]} أكثر فئتين شيوعًا من التوزيعات المسموح بها هما:

التوزيعات القابلة للحساب في زمن متعدد الحدود ( $P$ -computable): هي توزيعات يمكن حساب كثافتها التراكمية لأي مدخل $x$ مُعطى . بتعبير أدق، عند إعطاء توزيع احتمالي $μ$ وسلسلة $x \in {0, 1} n$ ، يمكن حساب القيمة $\mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]$ في وقت متعدد الحدود. وهذا يعني أن $احتمال [x]$ قابل للحساب أيضًا في وقت متعدد الحدود.
التوزيعات القابلة لأخذ العينات في وقت متعدد الحدود ( $P$ -samplable): هذه هي التوزيعات التي يمكن من خلالها سحب عينات عشوائية في وقت متعدد الحدود.

على الرغم من تشابه هاتين الصيغتين، إلا أنهما ليستا متكافئتين. فإذا كان التوزيع قابلاً للحساب من $الدرجة P،$ فإنه قابل للمعاينة من $الدرجة P$ أيضاً ، ولكن العكس غير صحيح إذا كانت $P$ ≠ P ≠ $P \neq$ P. ^{[ 7 ]}

متوسط الضغط ومتوسط المسافة بين نقاط البيع

تُصنَّف المسألة التوزيعية $(L, D)$ ضمن فئة التعقيد $AvgP$ إذا وُجدت خوارزمية فعّالة للحالة المتوسطة للمسألة $L$ ، كما هو مُعرَّف أعلاه. وتُسمى هذه الفئة أحيانًا $distP$ في $المراجع$ . ^{[ 7 ]}

تُصنَّف المسألة التوزيعية $(L, D)$ ضمن فئة التعقيد $distNP$ إذا كانت $L$ تنتمي إلى $فئة NP$ و $D$ قابلة للحساب من $فئة P.$ أما إذا كانت $L$ تنتمي إلى $فئة NP$ و $D قابلة لأخذ عينات من فئة$ $P$ ، فإن $(L, D)$ تنتمي إلى $فئة sampNP$ . ^{[ 7 ]}

$يشكل كل من AvgP$ و $distNP$ معًا نظائر الحالة المتوسطة لـ $P$ و $NP$ على التوالي. ^{[ 7 ]}

الاختزالات بين مسائل التوزيع

لنفترض أن $(L, D)$ و $(L', D')$ مسألتان توزيعيتان. تُختزل الحالة المتوسطة للمسألة $(L, D) إلى المسألة$ $(L', D')$ (وتُكتب $(L, D) \leq AvgP (L', D')$ ) إذا وُجدت دالة $f$ يمكن حسابها لكل $n$ ، عند إدخال $x ، في زمن متعدد الحدود بالنسبة لـ$ $n$ .

(صحة) $x \in L$ إذا وفقط إذا كان $f (x) \in L'$
(الهيمنة) توجد كثيرتا حدود $p$ و $m$ بحيث أنه لكل $n$ و $y$ ، $\sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(n)}(y)$

يفرض شرط الهيمنة فكرة أنه إذا كانت المسألة $(L, D)$ صعبة في المتوسط، فإن المسألة $(L', D')$ تكون صعبة أيضًا في المتوسط. وبشكل بديهي، ينبغي أن يوفر الاختزال طريقة لحل حالة $x$ من المسألة $L$ عن طريق حساب $f (x)$ وتغذية الخوارزمية التي تحل $L'$ بالناتج . بدون شرط الهيمنة، قد لا يكون ذلك ممكنًا، لأن الخوارزمية التي تحل $L$ في وقت متعدد الحدود في المتوسط قد تستغرق وقتًا أطول من متعدد الحدود على عدد قليل من المدخلات، ولكن قد تقوم $f$ بتحويل هذه المدخلات إلى مجموعة أكبر بكثير من $D'،$ بحيث لا تعمل الخوارزمية $A'$ في وقت متعدد الحدود في المتوسط. يسمح شرط الهيمنة فقط بظهور هذه السلاسل بشكل متعدد الحدود بنفس عدد مرات ظهورها في $D'$ . ^{[ 6 ]}

مسائل DistNP-complete

النظير المتوسط لمفهوم اكتمال $NP$ هو اكتمال $NP التوزيعي$ . تُعتبر مسألة التوزيع $(L', D') كاملة$ $من نوع distNP$ إذا كانت $(L', D')$ تنتمي إلى $distNP$ ، ولكل $(L, D)$ في $distNP$ ، يكون $(L, D)$ قابلاً للاختزال في الحالة المتوسطة إلى $(L', D')$ . ^{[ 7 ]}

من الأمثلة على مشكلة $distNP$ -complete مشكلة التوقف المحدود ، $(BH ، D)$ (لأي D قابلة للحساب من $النوع P$ ) المعرفة على النحو التالي:

$BH=\{(M,x,1^{t}):M{\text{ هي آلة تورينغ غير حتمية تقبل }}x{\text{ في }}\leq t{\text{ خطوات}}\}$ ^{[ 7 ]}

في ورقته البحثية الأصلية، عرض ليفين مثالاً على مسألة تبليط توزيعي تُصنف ضمن مسائل $NP-$ الكاملة في الحالة المتوسطة. ^{[ 5 ]} يتوفر على الإنترنت مسحٌ للمسائل المعروفة المصنفة ضمن مسائل $distNP- الكاملة.$ ^{[ 6 ]}

أحد مجالات البحث النشطة يتمثل في إيجاد مسائل جديدة $من نوع distNP$ -complete. إلا أن إيجاد هذه المسائل قد يكون معقدًا نظرًا لنتيجة غوريفيتش التي تُبين أن أي مسألة توزيعية ذات توزيع مسطح لا يمكن أن تكون $distNP$ -complete إلا إذا كان $EXP$ = $NEXP$ . ^{[ 8 ]} (التوزيع المسطح $μ$ هو توزيع يوجد له $ε > 0$ بحيث يكون لأي قيمة $x$ ، $μ (x) \leq 2 - | x | ε$ ). تُظهر نتيجة ليفني أن جميع مسائل $NP -complete الطبيعية لها نسخ$ $DistNP$ -complete. ^{[ 9 ]} مع ذلك، لم يتحقق بعد هدف إيجاد مسألة توزيعية طبيعية من نوع $DistNP -complete.$ ^{[ 10 ]}

التطبيقات

خوارزميات الفرز

كما ذُكر سابقًا، ركزت العديد من الدراسات المبكرة المتعلقة بتعقيد الحالة المتوسطة على المشكلات التي توجد لها خوارزميات ذات زمن متعدد الحدود، مثل الفرز. على سبيل المثال، تتميز العديد من خوارزميات الفرز التي تستخدم العشوائية، مثل Quicksort ، بزمن تشغيل في أسوأ الحالات يبلغ $O(n²) ، ولكن زمن تشغيل في$ الحالة المتوسطة يبلغ $O(n log(n))$ ، حيث $n$ هو طول المدخلات المراد فرزها. ^{[ 2 ]}

علم التشفير

في معظم المسائل، يُجرى تحليل التعقيد في الحالة المتوسطة لإيجاد خوارزميات فعّالة لمسألة تُعتبر صعبة في أسوأ الحالات. أما في التطبيقات التشفيرية، فالوضع معكوس: إذ لا يُعتدّ بتعقيد أسوأ الحالات؛ بل نريد ضمانًا بأن التعقيد في الحالة المتوسطة لكل خوارزمية "تخترق" نظام التشفير غير فعّال. ^{[ 11 ]}

لذا، تعتمد جميع أنظمة التشفير الآمنة على وجود دوال أحادية الاتجاه . ^{[ 3 ]} على الرغم من أن وجود هذه الدوال لا يزال مسألة مفتوحة ، فإن العديد من الدوال المرشحة تستند إلى مسائل معقدة مثل تحليل الأعداد الصحيحة إلى عواملها الأولية أو حساب اللوغاريتم المتقطع . تجدر الإشارة إلى أنه ليس من المرغوب فيه أن تكون الدالة المرشحة من $فئة NP-$ كاملة، لأن ذلك سيضمن فقط عدم وجود خوارزمية فعالة لحل المسألة في أسوأ الحالات؛ ما نريده فعليًا هو ضمان عدم قدرة أي خوارزمية فعالة على حل المسألة على مدخلات عشوائية (أي الحالة المتوسطة). في الواقع، تقع كل من مسألة تحليل الأعداد الصحيحة إلى عواملها الأولية ومسألة حساب اللوغاريتم المتقطع ضمن فئة $NP \cap$ $coNP$ ، وبالتالي لا يُعتقد أنها من فئة $NP-$ كاملة. ^{[ 7 ]} إن حقيقة أن علم التشفير برمته مبني على وجود مسائل غير قابلة للحل في الحالة المتوسطة ضمن $فئة NP$ هي أحد الدوافع الرئيسية لدراسة تعقيد الحالة المتوسطة.

نتائج أخرى

يوضح مبدأ ياو ، من ورقة بحثية نشرها أندرو ياو عام 1978 ، أنه بالنسبة لفئات واسعة من المسائل الحسابية، فإن تعقيد الحالة المتوسطة لتوزيع إدخال صعب وخوارزمية حتمية مُكيَّفة مع هذا التوزيع هو نفسه التعقيد المتوقع لخوارزمية عشوائية سريعة وأسوأ حالة إدخال لها. ^{[ 12 ]}

في عام 1990، أثبت إمباغليازو وليفين أنه إذا وُجدت خوارزمية فعّالة للحالة المتوسطة لمسألة كاملة من فئة $distNP$ تحت التوزيع المنتظم، فإنه توجد خوارزمية للحالة المتوسطة لكل مسألة في $فئة NP$ تحت أي توزيع قابل للمعاينة في زمن متعدد الحدود. ^{[ 13 ]} ولا يزال تطبيق هذه النظرية على مسائل التوزيع الطبيعية سؤالًا مفتوحًا لم يُبحث فيه بعد. ^{[ 3 ]}

في عام ١٩٩٢، أثبت بن ديفيد وآخرون أنه إذا كانت جميع اللغات في $مجموعة distNP$ تمتلك خوارزميات قرار جيدة في المتوسط، فإنها تمتلك أيضًا خوارزميات بحث جيدة في المتوسط. علاوة على ذلك، أظهروا أن هذه النتيجة صحيحة في ظل افتراض أضعف: إذا كانت كل لغة في $مجموعة NP$ سهلة في المتوسط لخوارزميات القرار بالنسبة للتوزيع المنتظم، فإنها تكون سهلة أيضًا في المتوسط لخوارزميات البحث بالنسبة للتوزيع المنتظم. ^{[ ١٤ ]} وبالتالي، لا يمكن أن توجد دوال تشفير أحادية الاتجاه إلا إذا كانت هناك مسائل $distNP$ على التوزيع المنتظم صعبة في المتوسط لخوارزميات القرار.

في عام 1993، أثبت فيجنباوم وفورتنو أنه لا يمكن إثبات، في ظل الاختزالات العشوائية غير التكيفية، أن وجود خوارزمية جيدة في المتوسط لمسألة $distNP-$ كاملة تحت التوزيع المنتظم يستلزم وجود خوارزميات فعالة في أسوأ الحالات لجميع المسائل في $NP$ . ^{[ 15 ]} وفي عام 2003، عمّم بوغدانوف وتريفيسان هذه النتيجة لتشمل الاختزالات غير التكيفية العشوائية. ^{[ 16 ]} تُظهر هذه النتائج أنه من غير المرجح إمكانية إقامة أي ارتباط بين تعقيد الحالة المتوسطة وتعقيد الحالة الأسوأ عبر الاختزالات. ^{[ 3 ]}

انظر أيضاً

مراجع

↑ غولدريتش، أوديد؛ فادان، ساليل (ديسمبر 2007). "عدد خاص حول تعقيد أسوأ الحالات مقابل تعقيد متوسط الحالات: مقدمة المحررين" . التعقيد الحسابي . 16 (4): 325-330 . doi : 10.1007/s00037-007-0232-y . ISSN 1016-3328 .
1 2 كورمين، توماس هـ؛ ليسرسون، تشارلز إي. ريفست، رونالد L.؛ شتاين، كليفورد (2009) [1990]. مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN 978-0-262-03384-8. OCLC 311310321 .
1 2 3 4 5 6 بوغدانوف، أندريه؛ تريفيسان، لوكا (2006). "تعقيد الحالة المتوسطة" . أسس واتجاهات في علوم الحاسوب النظرية . 2 (1): 1-106 . doi : 10.1561/0400000004 . ISSN 1551-305X .
↑ كنوت، دونالد (1973). فن برمجة الحاسوب . المجلد 3. أديسون-ويسلي.
1 2 ليفين، ليونيد أ. (فبراير 1986). "مسائل الحالة المتوسطة الكاملة" . مجلة SIAM للحوسبة . 15 (1): 285-286 . doi : 10.1137/0215020 . ISSN 0097-5397 .
1 2 3 وانغ، جي (1997). "نظرية التعقيد الحسابي في الحالة المتوسطة". في: هيماسپاندرا، لين أ.؛ سيلمان، آلان ل. (محرران). نظرية التعقيد: نظرة استرجاعية II (ملف PDF) . المجلد 2. سبرينغر ساينس آند بيزنس ميديا. الصفحات 295-328 .
1 2 3 4 5 6 7 8 9 أرورا، سانجيف؛ باراك، بواز (2009). "18. متوسط تعقيد الحالة: نظرية ليفين". التعقيد الحسابي: منهج حديث . كامبريدج؛ نيويورك: مطبعة جامعة كامبريدج.
↑ غوريفيتش، يوري (أكتوبر 1987). "مسائل NP العشوائية الكاملة وغير الكاملة". الندوة السنوية الثامنة والعشرون حول أسس علوم الحاسوب (SFCS 1987) . الصفحات 111-117 . doi : 10.1109/SFCS.1987.14 . ISBN 0-8186-0807-2.
↑ ليفني، نوام (ديسمبر 2010). "جميع مسائل NP-Complete الطبيعية لها نسخ كاملة في الحالة المتوسطة" . التعقيد الحسابي . 19 (4): 477-499 . doi : 10.1007/s00037-010-0298-9 . ISSN 1016-3328 .
↑ غولدريتش، أوديد (2011)، "ملاحظات حول نظرية ليفين لتعقيد الحالة المتوسطة" ، في غولدريتش، أوديد (محرر)، دراسات في التعقيد والتشفير. متفرقات حول التفاعل بين العشوائية والحساب ، سلسلة محاضرات في علوم الحاسوب، المجلد 6650، برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ، الصفحات 233-247 ، doi : 10.1007/978-3-642-22670-0_21 ، ISBN 978-3-642-22669-4تم الاطلاع عليه بتاريخ 21-05-2025
↑ كاتز، جوناثان؛ ليندل، يهودا (2021). مقدمة في التشفير الحديث . سلسلة تشابمان آند هول/سي آر سي للتشفير وأمن الشبكات ( الطبعة الثالثة). بوكا راتون، فلوريدا: مطبعة سي آر سي. رقم ISBN 978-1-351-13303-6.
↑ ياو، أندرو (1977)، "الحسابات الاحتمالية: نحو مقياس موحد للتعقيد"، وقائع الندوة الثامنة عشرة لمعهد مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب (FOCS) ، الصفحات 222-227 ، doi : 10.1109/SFCS.1977.24
↑ R. Impagliazzo و L. Levin، "لا توجد طرق أفضل لتوليد حالات NP الصعبة من الاختيار بشكل عشوائي منتظم"، في وقائع الندوة الحادية والثلاثين لمعهد مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب، ص 812-821، 1990.
↑ بن ديفيد، س.؛ تشور، ب.؛ غولدريتش، أ. (1989). "حول نظرية تعقيد الحالة المتوسطة" . وقائع الندوة السنوية الحادية والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '89 . مطبعة جمعية آلات الحوسبة. الصفحات 204-216 . doi : 10.1145/73007.73027 . ISBN 978-0-89791-307-2.
↑ فيجنباوم، جوان؛ فورتناو، لانس (أكتوبر 1993). "الاختزال الذاتي العشوائي للمجموعات الكاملة" . مجلة SIAM للحوسبة . 22 (5): 994-1005 . doi : 10.1137/0222061 . ISSN 0097-5397 .
↑ بوغدانوف، أندريه؛ تريفيسان، لوكا (يناير 2006). "حول اختزال أسوأ الحالات إلى متوسط الحالات لمسائل NP" . مجلة SIAM للحوسبة . 36 (4): 1119-1159 . doi : 10.1137/S0097539705446974 . ISSN 0097-5397 .

للمزيد من القراءة

العروض التقديمية التربوية:

إمباغليازو، ر. (1995). "نظرة شخصية على تعقيد الحالة المتوسطة". وقائع مؤتمر "البنية في نظرية التعقيد". المؤتمر السنوي العاشر لجمعية مهندسي الكهرباء والإلكترونيات. مطبعة جمعية مهندسي الكهرباء والإلكترونيات للحاسوب. ص 134-147 . doi : 10.1109/SCT.1995.514853 . ISBN 978-0-8186-7052-7.
وانغ، جي (1997). "نظرية التعقيد الحسابي في الحالة المتوسطة". في: هيماسباندرا، لين أ.؛ سيلمان، آلان ل. (محرران). نظرية التعقيد: نظرة استرجاعية II (ملف PDF) . المجلد 2. سبرينغر ساينس آند بيزنس ميديا. الصفحات 295-328 .
جولدرايش، أوديد (2011)، "تعقيد الحالة المتوسطة، مُعاد النظر فيه" (ملف PDF) ، في جولدرايش، أوديد (محرر)، دراسات في التعقيد والتشفير. متفرقات حول التفاعل بين العشوائية والحساب ، سلسلة محاضرات في علوم الحاسوب، المجلد 6650، برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ، الصفحات 422-450 ، doi : 10.1007/978-3-642-22670-0_29 ، ISBN 978-3-642-22669-4
أرورا، سانجيف؛ باراك، بواز (2009). "18. تعقيد الحالة المتوسطة: نظرية ليفين". التعقيد الحسابي: منهج حديث . كامبريدج؛ نيويورك: مطبعة جامعة كامبريدج.

تشمل الأدبيات المتعلقة بتعقيد الحالة المتوسطة الأعمال التالية:

ليفين، ليونيد (1986)، "مسائل الحالة المتوسطة الكاملة"، مجلة SIAM للحوسبة ، 15 (1): 285-286 ، doi : 10.1137/0215020
فرانكو، جون (1986)، "حول الأداء الاحتمالي للخوارزميات لمسألة الإرضاء"، رسائل معالجة المعلومات ، 23 (2): 103-106 ، doi : 10.1016/0020-0190(86)90051-7..
فلاجوليه, فيليب ; Vitter, JS (أغسطس 1987)، تحليل الحالة المتوسطة للخوارزميات وهياكل البيانات ، Tech. تقرير، المعهد الوطني للبحوث المعلوماتية والآلية، BP 105-78153 Le Chesnay Cedex فرنسا.
غوريفيتش، يوري ؛ شيلاه، ساهارون (1987)، "الوقت الحسابي المتوقع لمسألة المسار الهاميلتوني "، مجلة SIAM للحوسبة ، 16 (3): 486-502 ، CiteSeerX 10.1.1.359.8982 ، doi : 10.1137/0216034 .
بن ديفيد، شاي؛ تشور، بيني ؛ غولدريتش، عوديد ؛ لوبي، مايكل ( 1989)، "حول نظرية تعقيد الحالة المتوسطة"، وقائع الندوة السنوية الحادية والعشرين حول نظرية الحوسبة ، رابطة آلات الحوسبة ، الصفحات 204-216 .
غوريفيتش، يوري (1991)، "اكتمال الحالة المتوسطة"، مجلة علوم الحاسوب والنظم ، 42 (3): 346-398 ، doi : 10.1016/0022-0000(91)90007-R ، hdl : 2027.42/29307انظر أيضًا مسودة عام 1989 .
سيلمان، ب.؛ ميتشل، د.؛ ليفيسك، هـ. ( 1992)، "التوزيعات الصعبة والسهلة لمسائل SAT"، وقائع المؤتمر الوطني العاشر حول الذكاء الاصطناعي ، ص 459-465 .
شولر، راينر؛ ياماكامي، تومويوكي (1992)، "تعقيد الحالة المتوسطة الهيكلية"، وقائع مؤتمر أسس تكنولوجيا البرمجيات وعلوم الحاسوب النظرية ، سلسلة محاضرات في علوم الحاسوب، المجلد 652، سبرينغر-فيرلاغ، الصفحات 128-139 .
رايشوك، روديجر؛ شيندلهاور، كريستيان ( 1993)، "تعقيد الحالة المتوسطة الدقيق"، وقائع الندوة السنوية العاشرة حول الجوانب النظرية لعلوم الحاسوب ، ص 650-661 .
فينكاتيسان، ر.؛ راجاغوبالان، س. ( 1992)، "صعوبة حل مسائل المصفوفات والديوفانتين في الحالة المتوسطة"، وقائع الندوة السنوية الرابعة والعشرين حول نظرية الحوسبة ، رابطة آلات الحوسبة ، ص 632-642 .
كوكس، جيم؛ إريكسون، لارس؛ ميشرا، باد (1995)، متوسط تعقيد الحالات في القياس المنطقي متعدد المستويات (ملف PDF) ، تقرير فني TR1995-711، قسم علوم الحاسوب، جامعة نيويورك.

[gol07-1] غولدريتش، أوديد؛ فادان، ساليل (ديسمبر 2007). "عدد خاص حول تعقيد أسوأ الحالات مقابل تعقيد متوسط الحالات: مقدمة المحررين" . التعقيد الحسابي . 16 (4): 325-330 . doi : 10.1007/s00037-007-0232-y . ISSN 1016-3328 .

[clrs-2] 1 2 كورمين، توماس هـ؛ ليسرسون، تشارلز إي. ريفست، رونالد L.؛ شتاين، كليفورد (2009) [1990]. مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN 978-0-262-03384-8. OCLC 311310321 .

[bog06-3] 1 2 3 4 5 6 بوغدانوف، أندريه؛ تريفيسان، لوكا (2006). "تعقيد الحالة المتوسطة" . أسس واتجاهات في علوم الحاسوب النظرية . 2 (1): 1-106 . doi : 10.1561/0400000004 . ISSN 1551-305X .

[knu73-4] كنوت، دونالد (1973). فن برمجة الحاسوب . المجلد 3. أديسون-ويسلي.

[levin86-5] 1 2 ليفين، ليونيد أ. (فبراير 1986). "مسائل الحالة المتوسطة الكاملة" . مجلة SIAM للحوسبة . 15 (1): 285-286 . doi : 10.1137/0215020 . ISSN 0097-5397 .

[wangsurvey-6] 1 2 3 وانغ، جي (1997). "نظرية التعقيد الحسابي في الحالة المتوسطة". في: هيماسپاندرا، لين أ.؛ سيلمان، آلان ل. (محرران). نظرية التعقيد: نظرة استرجاعية II (ملف PDF) . المجلد 2. سبرينغر ساينس آند بيزنس ميديا. الصفحات 295-328 .

[ab09-7] 1 2 3 4 5 6 7 8 9 أرورا، سانجيف؛ باراك، بواز (2009). "18. متوسط تعقيد الحالة: نظرية ليفين". التعقيد الحسابي: منهج حديث . كامبريدج؛ نيويورك: مطبعة جامعة كامبريدج.

[gur87-8] غوريفيتش، يوري (أكتوبر 1987). "مسائل NP العشوائية الكاملة وغير الكاملة". الندوة السنوية الثامنة والعشرون حول أسس علوم الحاسوب (SFCS 1987) . الصفحات 111-117 . doi : 10.1109/SFCS.1987.14 . ISBN 0-8186-0807-2.

[livne06-9] ليفني، نوام (ديسمبر 2010). "جميع مسائل NP-Complete الطبيعية لها نسخ كاملة في الحالة المتوسطة" . التعقيد الحسابي . 19 (4): 477-499 . doi : 10.1007/s00037-010-0298-9 . ISSN 1016-3328 .

[gol97-10] غولدريتش، أوديد (2011)، "ملاحظات حول نظرية ليفين لتعقيد الحالة المتوسطة" ، في غولدريتش، أوديد (محرر)، دراسات في التعقيد والتشفير. متفرقات حول التفاعل بين العشوائية والحساب ، سلسلة محاضرات في علوم الحاسوب، المجلد 6650، برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ، الصفحات 233-247 ، doi : 10.1007/978-3-642-22670-0_21 ، ISBN 978-3-642-22669-4تم الاطلاع عليه بتاريخ 21-05-2025

[katz07-11] كاتز، جوناثان؛ ليندل، يهودا (2021). مقدمة في التشفير الحديث . سلسلة تشابمان آند هول/سي آر سي للتشفير وأمن الشبكات ( الطبعة الثالثة). بوكا راتون، فلوريدا: مطبعة سي آر سي. رقم ISBN 978-1-351-13303-6.

[12] ياو، أندرو (1977)، "الحسابات الاحتمالية: نحو مقياس موحد للتعقيد"، وقائع الندوة الثامنة عشرة لمعهد مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب (FOCS) ، الصفحات 222-227 ، doi : 10.1109/SFCS.1977.24

[imp90-13] R. Impagliazzo و L. Levin، "لا توجد طرق أفضل لتوليد حالات NP الصعبة من الاختيار بشكل عشوائي منتظم"، في وقائع الندوة الحادية والثلاثين لمعهد مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب، ص 812-821، 1990.

[bd92-14] بن ديفيد، س.؛ تشور، ب.؛ غولدريتش، أ. (1989). "حول نظرية تعقيد الحالة المتوسطة" . وقائع الندوة السنوية الحادية والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '89 . مطبعة جمعية آلات الحوسبة. الصفحات 204-216 . doi : 10.1145/73007.73027 . ISBN 978-0-89791-307-2.

[ff93-15] فيجنباوم، جوان؛ فورتناو، لانس (أكتوبر 1993). "الاختزال الذاتي العشوائي للمجموعات الكاملة" . مجلة SIAM للحوسبة . 22 (5): 994-1005 . doi : 10.1137/0222061 . ISSN 0097-5397 .

[bog03-16] بوغدانوف، أندريه؛ تريفيسان، لوكا (يناير 2006). "حول اختزال أسوأ الحالات إلى متوسط الحالات لمسائل NP" . مجلة SIAM للحوسبة . 36 (4): 1119-1159 . doi : 10.1137/S0097539705446974 . ISSN 0097-5397 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ ١٤ ]

[ 15 ]

[ 16 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗