تعقيدات التواصل

الموسوعة الحرة

في علم الحاسوب النظري ، يدرس تعقيد الاتصال مقدار الاتصال اللازم لحل مشكلة ما عندما تتوزع مدخلات هذه المشكلة بين طرفين أو أكثر. وقد طُرح مفهوم تعقيد الاتصال لأول مرة من قِبل أندرو ياو عام 1979، أثناء دراسته لمشكلة الحوسبة الموزعة على عدة أجهزة. [ 1 ] تُصاغ المشكلة عادةً على النحو التالي: يتلقى طرفان (يُطلق عليهما تقليديًا أليس وبوب ) مدخلات (قد تكون مختلفة).ن{\displaystyle n}- سلسلة بتx{\displaystyle x}وy{\displaystyle y}الهدف هو أن تقوم أليس بحساب قيمة دالة معينة.و(x،y){\displaystyle f(x,y)}يعتمد ذلك على كليهماx{\displaystyle x}وy{\displaystyle y}، بأقل قدر من التواصل بينهما.

بينما يمكن لأليس وبوب دائمًا أن ينجحا من خلال إرسال بوب كاملن{\displaystyle n}سلسلة بتات إلى أليس (التي تقوم بعد ذلك بحساب الدالة)و{\displaystyle f}الفكرة هنا هي إيجاد طرق ذكية للحساب.و{\displaystyle f}بأقل منن{\displaystyle n}أجزاء من الاتصال. تجدر الإشارة إلى أنه، على عكس نظرية التعقيد الحسابي ، فإن تعقيد الاتصال لا يهتم بكمية العمليات الحسابية التي تقوم بها أليس أو بوب، أو بحجم الذاكرة المستخدمة ، حيث أننا لا نفترض عمومًا أي شيء عن القدرة الحسابية لأي منهما.

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

التعريف الرسمي

يتركو:X×Y→Z{\displaystyle f:X\times Y\rightarrow Z}حيث نفترض في الحالة النموذجية أنX=Y={0،1}ن{\displaystyle X=Y=\{0,1\}^{n}}وZ={0،1}{\displaystyle Z=\{0,1\}}أليس تحملن{\displaystyle n}سلسلة بت x∈X{\displaystyle x\in X}بينما يحمل بوبن{\displaystyle n}سلسلة بت y∈Y{\displaystyle y\in Y}من خلال التواصل مع بعضهما البعض بتًا واحدًا في كل مرة (اعتماد بروتوكول اتصال متفق عليه مسبقًا)، ترغب أليس وبوب في حساب قيمةو(x،y){\displaystyle f(x,y)}بحيث يعرف أحد الطرفين على الأقل القيمة في نهاية الاتصال. عند هذه النقطة، يمكن إرسال الإجابة مرة أخرى، بحيث يعرف كلا الطرفين الإجابة مقابل بت إضافي واحد. يمثل هذا أسوأ حالة لتعقيد الاتصال في مشكلة الاتصال هذه في الحوسبة.و{\displaystyle f}، المشار إليه بـد(و){\displaystyle D(f)}، ثم يُعرَّف بأنه

د(و)={\displaystyle D(f)=}الحد الأدنى لعدد البتات المتبادلة بين أليس وبوب في أسوأ الحالات.

كما لوحظ أعلاه، بالنسبة لأي دالةو:{0،1}ن×{0،1}ن→{0،1}{\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}لديناد(و)≤ن{\displaystyle D(f)\leq n}باستخدام التعريف أعلاه، من المفيد التفكير في الوظيفةو{\displaystyle f}كمصفوفة​أ{\displaystyle A}(تسمى مصفوفة الإدخال أو مصفوفة الاتصال ) حيث يتم فهرسة الصفوف بواسطةx∈X{\displaystyle x\in X}والأعمدة بواسطةy∈Y{\displaystyle y\in Y}عناصر المصفوفة هيأx،y=و(x،y){\displaystyle A_{x,y}=f(x,y)}في البداية، كان لدى كل من أليس وبوب نسخة من المصفوفة بأكملها.أ{\displaystyle A}(بافتراض الدالة)و{\displaystyle f}إذا كان كلا الطرفين على علمٍ بالدالة، فيمكن إعادة صياغة مشكلة حساب قيمة الدالة على أنها "تحديد القيمة الصفرية" بناءً على عنصر المصفوفة المقابل. ويمكن حل هذه المشكلة إذا كان كل من أليس وبوب على علمٍ بالدالة.x{\displaystyle x}وy{\displaystyle y}في بداية عملية الاتصال، يكون عدد الخيارات المتاحة لموقع المصفوفة المقابل للمدخلات مساوياً لحجم المصفوفة، أي22ن{\displaystyle 2^{2n}}ثم، عندما يتواصل كل طرف مع الآخر، يقل عدد الخيارات المتاحة للموقع، حيث يؤدي ذلك إلى حذف مجموعة من الصفوف/الأعمدة، مما ينتج عنه مصفوفة فرعية منأ{\displaystyle A}.

بصورة أكثر رسمية، مجموعةR⊆X×Y{\displaystyle R\subseteq X\times Y}يُطلق عليه اسم مستطيل (توافقي) إذا كان كلما(x1،y1)∈R{\displaystyle (x_{1},y_{1})\in R}و(x2،y2)∈R{\displaystyle (x_{2},y_{2})\in R}ثم(x1،y2)∈R{\displaystyle (x_{1},y_{2})\in R}أو بعبارة أخرى،R{\displaystyle R}يكون مستطيلاً توافقياً إذا أمكن التعبير عنه على النحو التاليR=م×شمال{\displaystyle R=M\times N}بالنسبة للبعضم⊆X{\displaystyle M\subseteq X}وشمال⊆Y{\displaystyle N\subseteq Y}ضع في اعتبارك الحالة عندماك{\displaystyle k}تم تبادل البيانات بالفعل بين الطرفين. الآن، بالنسبة لـ...ح∈{0،1}ك{\displaystyle h\in \{0,1\}^{k}}لنقم بتعريف مصفوفة

تيح={(x،y): ال ك- بتات يتم تبادلها عند الإدخال (x،y) يكون ح}{\displaystyle T_{h}=\{(x,y):{\text{ the }}k{\text{-bits exchanged on input }}(x,y){\text{ is }}h\}}

ثمتيح⊆X×Y{\displaystyle T_{h}\subseteq X\times Y}وليس من الصعب إثبات ذلكتيح{\displaystyle T_{h}}هو مستطيل توافقي فيأ{\displaystyle A}.

مثال: معادلة عاطفية

ندرس الحالة التي يحاول فيها أليس وبوب تحديد ما إذا كانت سلاسل الإدخال الخاصة بهما متساوية أم لا. ونُعرّف رسميًا دالة المساواة ، التي يُرمز لها بـهـسؤال:{0،1}ن×{0،1}ن→{0،1}{\displaystyle EQ:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}، بواسطةهـسؤال(x،y)=1{\displaystyle EQ(x,y)=1}لوx=y{\displaystyle x=y}كما سنوضح أدناه، فإن أي بروتوكول اتصال حتمي يحلهـسؤال{\displaystyle EQ}يتطلبن{\displaystyle n}أجزاء من التواصل في أسوأ الأحوال. كمثال تمهيدي، لنأخذ الحالة البسيطة لـx،y∈{0،1}3{\displaystyle x,y\in \{0,1\}^{3}}يمكن تمثيل دالة المساواة في هذه الحالة بالمصفوفة أدناه. تمثل الصفوف جميع الاحتمالات.x{\displaystyle x}، الأعمدة تلك الخاصةy{\displaystyle y}.

معادلة عاطفية٠٠٠001010011100101110111
٠٠٠10000000
00101000000
01000100000
01100010000
10000001000
10100000100
11000000010
11100000001

في هذا الجدول، لا تُقيّم الدالة إلى 1 إلا عندماx{\displaystyle x}يساويy{\displaystyle y}(أي، على القطر). ومن السهل أيضًا أن نرى كيف أن نقل بت واحد يقسم إمكانيات شخص ما إلى النصف. عندما يكون البت الأول منy{\displaystyle y}إذا كانت القيمة 1، فضع في اعتبارك نصف الأعمدة فقط (حيثy{\displaystyle y}(يمكن أن يساوي 100 أو 101 أو 110 أو 111).

النظرية: D(EQ) = n

البرهان. افترض أند(هـسؤال)≤ن-1{\displaystyle D(EQ)\leq n-1}وهذا يعني أنه يوجدx≠x′{\displaystyle x\neq x'}بحيث(x،x){\displaystyle (x,x)}و(x′،x′){\displaystyle (x',x')}يجب أن يكون لديهم نفس نص المحادثةح{\displaystyle h}بما أن هذا النص يحدد مستطيلاً،و(x،x′){\displaystyle f(x,x')}يجب أن يكون أيضًا 1. بحسب التعريفx≠x′{\displaystyle x\neq x'}ونحن نعلم أن المساواة لا تتحقق إلا لـ(أ،ب){\displaystyle (a,b)}متىأ=ب{\displaystyle a=b}وهذا يؤدي إلى تناقض.

تُسمى هذه التقنية لإثبات الحدود الدنيا للاتصال الحتمي بتقنية مجموعة الخداع . [ 2 ]

تعقيد الاتصال العشوائي

في التعريف أعلاه، نهتم بعدد البتات التي يجب نقلها بشكل حتمي بين طرفين. إذا أُتيح لكلا الطرفين الوصول إلى مولد أرقام عشوائية ، فهل يمكنهما تحديد قيمة...و{\displaystyle f}مع تبادل معلومات أقل بكثير؟ يجيب ياو، في ورقته البحثية الرائدة [ 1 ]، على هذا السؤال من خلال تعريف تعقيد الاتصال العشوائي .

بروتوكول عشوائيR{\displaystyle R}لوظيفةو{\displaystyle f}يحتوي على خطأ من جانبين.

برو[R(x،y)=0]>23،لوو(x،y)=0{\displaystyle \Pr[R(x,y)=0]>{\frac {2}{3}},{\textrm {إذا}}\,f(x,y)=0}
برو[R(x،y)=1]>23،لوو(x،y)=1{\displaystyle \Pr[R(x,y)=1]>{\frac {2}{3}},{\textrm {إذا}}\,f(x,y)=1}

البروتوكول العشوائي هو بروتوكول حتمي يستخدم سلسلة عشوائية إضافية إلى جانب مدخلاته المعتادة. يوجد نموذجان لهذا: السلسلة العامة، وهي سلسلة عشوائية يعرفها الطرفان مسبقًا، والسلسلة الخاصة، التي يُنشئها أحد الطرفين ويجب إبلاغها للطرف الآخر. تُبين النظرية الموضحة أدناه أنه يمكن محاكاة أي بروتوكول سلسلة عامة ببروتوكول سلسلة خاصة يستخدم O(log n) بتًا إضافيًا مقارنةً بالبروتوكول الأصلي.

في متباينات الاحتمالات المذكورة أعلاه، يُفهم أن نتيجة البروتوكول تعتمد فقط على السلسلة العشوائية؛ إذ تبقى كلتا السلسلتين x و y ثابتتين. بعبارة أخرى، إذا كانت R ( x , y ) تُنتج g ( x , y , r ) عند استخدام السلسلة العشوائية r ، فإن g ( x , y , r ) = f ( x , y ) لما لا يقل عن ثلثي جميع خيارات السلسلة r .

يتم تعريف التعقيد العشوائي ببساطة على أنه عدد البتات المتبادلة في مثل هذا البروتوكول.

لاحظ أنه من الممكن أيضًا تعريف بروتوكول عشوائي بخطأ من جانب واحد، ويتم تعريف التعقيد بشكل مماثل.

مثال: معادلة عاطفية

بالعودة إلى المثال السابق للمساواة ، إذا لم يكن اليقين مطلوبًا، فيمكن لأليس وبوب التحقق من المساواة باستخدام ⁠يا(سجل⁡ن){\displaystyle O(\log n)}الرسائل . ضع في اعتبارك البروتوكول التالي: افترض أن أليس وبوب لديهما إمكانية الوصول إلى نفس السلسلة العشوائيةz∈{0،1}ن{\displaystyle z\in \{0,1\}^{n}}أليس تحسبz⋅x{\displaystyle z\cdot x}ويرسل هذه البتة (لنسميها b ) إلى بوب. (الـ(⋅){\displaystyle (\cdot )}(الضرب النقطي في GF(2) ). ثم يقارن بوب b بـz⋅y{\displaystyle z\cdot y}إذا كانا متساويين، فإن بوب يقبل، قائلاً إن س يساوي ص . وإلا، فإنه يرفض.

من الواضح، إذاx=y{\displaystyle x=y}، ثمz⋅x=z⋅y{\displaystyle z\cdot x=z\cdot y}، لذاPرoبz[أججهـصت]=1{\displaystyle Prob_{z[قبول]=1}إذا لم تكن قيمة x تساوي قيمة y ، فمن الممكن مع ذلك أنz⋅x=z⋅y{\displaystyle z\cdot x=z\cdot y}وهذا من شأنه أن يعطي بوب إجابة خاطئة. كيف يحدث هذا؟

إذا لم تكن قيمتا x و y متساويتين، فلا بد أنهما تختلفان في بعض المواقع:

{x=ج1ج2...ص...ص′...xنy=ج1ج2...q...q′...yنz=z1z2...zأنا...zج...zن{\displaystyle {\begin{cases}x=c_{1}c_{2}\ldots p\ldots p'\ldots x_{n}\\y=c_{1}c_{2}\ldots q\ldots q'\ldots y_{n}\\z=z_{1}z_{2}\ldots z_{i}\ldots z_{j}\ldots z_{n}\end{cases}}}

حيث يتفق x و y ،zأنا*xأنا=zأنا*جأنا=zأنا*yأنا{\displaystyle z_{i}*x_{i}=z_{i}*c_{i}=z_{i}*y_{i}}لذا، تؤثر هذه الحدود على حاصل الضرب النقطي بالتساوي. يمكننا تجاهل هذه الحدود بأمان والنظر فقط إلى موضع اختلاف x و y . علاوة على ذلك، يمكننا تبديل البتات.xأنا{\displaystyle x_{i}}وyأنا{\displaystyle y_{i}}دون تغيير ما إذا كانت حاصلات الضرب النقطي متساوية أم لا. هذا يعني أنه يمكننا تبديل البتات بحيث يحتوي x على أصفار فقط و y على آحاد فقط.

{x′=٠٠...0y′=11...1z′=z1z2...zن′{\displaystyle {\begin{cases}x'=00\ldots 0\\y'=11\ldots 1\\z'=z_{1}z_{2}\ldots z_{n'}\end{cases}}}

لاحظ أنz′⋅x′=0{\displaystyle z'\cdot x'=0}وz′⋅y′=Σأناzأنا′{\displaystyle z'\cdot y'=\Sigma _{i}z'_{i}}والآن، يصبح السؤال: بالنسبة لسلسلة عشوائية ماz′{\displaystyle z'}ما هو احتمال أنΣأناzأنا′=0{\displaystyle \Sigma _{i}z'_{i}=0}؟ بما أن كلzأنا′{\displaystyle z'_{i}}من المرجح بنفس القدر أن يكونصفر أو1 ، هذا الاحتمال هو فقط1/2{\displaystyle 1/2}وبالتالي، عندما لا تساوي x قيمة y ، Pرoبz[أججهـصت]=1/2{\displaystyle Prob_{z}[Accept]=1/2}يمكن تكرار الخوارزمية عدة مرات لزيادة دقتها، وهذا يفي بمتطلبات خوارزمية الاتصال العشوائي.

هذا يوضح أنه إذا تشاركت أليس وبوب سلسلة عشوائية بطول n ، فيمكنهما إرسال بت واحد إلى بعضهما البعض لحسابهـسؤال(x،y){\displaystyle EQ(x,y)}في القسم التالي، سيتبين أن أليس وبوب لا يستطيعان التبادل إلايا(سجل⁡ن){\displaystyle O(\log n)}بتات تُعادل في جودتها مشاركة سلسلة عشوائية بطول n . وبمجرد إثبات ذلك،يُمكن حساب EQ فييا(سجل⁡ن){\displaystyle O(\log n)}الرسائل .

مثال: GH

للحصول على مثال آخر على تعقيد الاتصال العشوائي، ننتقل إلى مثال يُعرف باسم مشكلة فجوة هامينغ (المختصرة GH ). رسميًا، يحتفظ كل من أليس وبوب برسائل ثنائية،x،y∈{-1،+1}ن{\displaystyle x,y\in \{-1,+1\}^{n}}ويرغبون في تحديد ما إذا كانت السلاسل متشابهة جدًا أم لا. وعلى وجه الخصوص، يرغبون في إيجاد بروتوكول اتصال يتطلب إرسال أقل عدد ممكن من البتات لحساب الدالة المنطقية الجزئية التالية.

جي إتشن(x،y):={-1⟨x،y⟩≤ن+1⟨x،y⟩≥ن.{\displaystyle {\text{GH}}_{n}(x,y):={\begin{cases}-1&\langle x,y\rangle \leq {\sqrt {n}}\\+1&\langle x,y\rangle \geq {\sqrt {n}}.\end{cases}}}

من الواضح أنه يجب عليهم تبادل جميع بياناتهم إذا كان البروتوكول حتميًا (وذلك لأنه إذا كانت هناك مجموعة فرعية حتمية ودقيقة من المؤشرات التي تنقلها أليس وبوب إلى بعضهما البعض، فتخيل وجود زوج من السلاسل النصية التي تختلف في تلك المجموعة).ن-1{\displaystyle {\sqrt {n}}-1}المواقف. إذا حدث خلاف آخر في أي موقف ولم يتم إبلاغه، فإن ذلك يؤثر على نتيجةجي إتشن(x،y){\displaystyle {\text{GH}}_{n}(x,y)}وبالتالي سيؤدي ذلك إلى إجراء غير صحيح.

والسؤال الطبيعي الذي يطرحه المرء حينها هو: هل يُسمح لنا بالخطأ؟1/3{\displaystyle 1/3}من الوقت (على حالات عشوائية)x،y{\displaystyle x,y}تم اختيارهم عشوائياً وبشكل منتظم من{-1،+1}ن{\displaystyle \{-1,+1\}^{n}}إذاً، هل يمكننا استخدام بروتوكول بعدد بتات أقل؟ اتضح أن الإجابة، بشكل مفاجئ إلى حد ما، هي لا، وذلك بفضل نتيجة توصل إليها تشاكرابارتي وريجيف عام 2012: فقد أظهرا أنه بالنسبة للحالات العشوائية، فإن أي إجراء صحيح على الأقل2/3{\displaystyle 2/3}يجب إرسال الوقتΩ(ن){\displaystyle \Omega (n)}أجزاء من الاتصالات، أي أنها جميعها تقريباً.

العملات العامة مقابل العملات الخاصة

يصبح إنشاء بروتوكولات عشوائية أسهل عندما يمتلك الطرفان نفس السلسلة العشوائية، وهو ما يُعرف ببروتوكول السلسلة المشتركة. مع ذلك، حتى في حال عدم امتلاك الطرفين لسلسلة عشوائية مشتركة، يظل من الممكن استخدام بروتوكولات السلاسل الخاصة بتكلفة اتصال منخفضة. يمكن محاكاة أي بروتوكول سلسلة عشوائية مشترك، باستخدام أي عدد من السلاسل العشوائية، بواسطة بروتوكول سلسلة خاصة يستخدم عددًا إضافيًا من البتات قدره O(log n) .

بشكل بديهي، يمكننا إيجاد مجموعة من السلاسل النصية تحتوي على قدر كافٍ من العشوائية لتشغيل بروتوكول العشوائية مع زيادة طفيفة في الخطأ. يمكن مشاركة هذه المجموعة مسبقًا، وبدلًا من اختيار سلسلة عشوائية، يكفي أن يتفق أليس وبوب على السلسلة التي سيختارانها من المجموعة المشتركة. هذه المجموعة صغيرة بما يكفي لتسهيل عملية التواصل بشأن الاختيار. يلي ذلك برهان رسمي .

لنفترض بروتوكولًا عشوائيًا P بمعدل خطأ أقصى قدره 0.1.R{\displaystyle R}يكون100ن{\displaystyle 100n}سلاسل بطول n ، مرقمةر1،ر2،...،ر100ن{\displaystyle r_{1},r_{2},\dots ,r_{100n}}بالنظر إلى مثل هذاR{\displaystyle R}، تعريف بروتوكول جديدPR′{\displaystyle P'_{R}}التي تختار بعضًا بشكل عشوائيرأنا{\displaystyle r_{i}}ثم يقوم بتشغيل P باستخدامرأنا{\displaystyle r_{i}}باعتبارها سلسلة عشوائية مشتركة. يتطلب الأمر O (log  100 n ) = O (log n ) بتًا لتوصيل اختيار رأنا{\displaystyle r_{i}}.

لنعرّفص(x،y){\displaystyle p(x,y)}وصR′(x،y){\displaystyle p'_{R}(x,y)}أن تكون الاحتمالات التيP{\displaystyle P}وPR′{\displaystyle P'_{R}} احسب القيمة الصحيحة للمدخل(x،y){\displaystyle (x,y)}.

مقابل مبلغ ثابت(x،y){\displaystyle (x,y)}يمكننا استخدام متباينة هوفدينغ للحصول على المعادلة التالية:

بروR[|صR′(x،y)-ص(x،y)|≥0.1]≤2خبرة⁡(-2(0.1)2⋅100ن)<2-2ن{\displaystyle \Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}}

لذلك عندما لا نملك(x،y){\displaystyle (x,y)}مُثَبَّت:

بروR[∃(x،y): |صR′(x،y)-ص(x،y)|≥0.1]≤∑(x،y)بروR[|صR′(x،y)-ص(x،y)|≥0.1]<∑(x،y)2-2ن=1{\displaystyle \Pr _{R}[\exists (x,y):\ |p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq \sum _{(x,y)}\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]<\sum _{(x,y)}2^{-2n}=1}

المساواة الأخيرة أعلاه صحيحة لوجود22ن{\displaystyle 2^{2n}}أزواج مختلفة(x،y){\displaystyle (x,y)}بما أن الاحتمال لا يساوي 1، فهناك بعضR0{\displaystyle R_{0}}حتى يكون ذلك للجميع(x،y){\displaystyle (x,y)}:

|صR0′(x،y)-ص(x،y)|<0.1{\displaystyle |p'_{R_{0}}(x,y)-p(x,y)|<0.1}

منذP{\displaystyle P}احتمال الخطأ لا يتجاوز 0.1،PR0′{\displaystyle P'_{R_{0}}}يمكن أن يكون احتمال الخطأ 0.2 كحد أقصى.

انهيار تعقيد الاتصال العشوائي

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

تعريف. موردR{\displaystyle R}يُقال إنها "تنهار" إذا، باستخدام ذلك الموردR{\displaystyle R}يكفي جزء واحد فقط من التواصل الكلاسيكي لكي تعرف أليس التقييمو(x،y){\displaystyle f(x,y)}في أسوأ سيناريو لأي دالة منطقيةو{\displaystyle f}.

إن الحقيقة المدهشة لانهيار تعقيد الاتصالات هي أن الوظيفةو{\displaystyle f}يمكن أن يكون حجم الإدخال كبيرًا بشكل تعسفي، ولكن يظل عدد بتات الاتصال ثابتًا عند بت واحد.

تُظهر بعض الموارد أنها غير قابلة للانهيار، مثل الارتباطات الكمومية [ 3 ] أو بشكل أعم الارتباطات شبه الكمومية [ 4 ]، بينما على النقيض من ذلك، تُظهر موارد أخرى أنها تُؤدي إلى انهيار تعقيد الاتصال العشوائي، مثل صندوق PR [ 5 ] أو بعض صناديق PR المشوشة التي تُحقق شروطًا معينة [ 6 ] [ 7 ] [ 8 ] .

التعقيد التوزيعي

يتمثل أحد أساليب دراسة تعقيد الاتصالات العشوائية في دراسة التعقيد التوزيعي.

بافتراض التوزيع المشتركμ{\displaystyle \mu }بناءً على مدخلات كلا اللاعبين، فإن التعقيد التوزيعي المقابل للدالةو{\displaystyle f}يمثل الحد الأدنى لتكلفة البروتوكول الحتميR{\displaystyle R}بحيثبرو[و(x،y)=R(x،y)]≥2/3{\displaystyle \Pr[f(x,y)=R(x,y)]\geq 2/3}حيث يتم أخذ عينات من المدخلات وفقًا لـμ{\displaystyle \mu }.

ينص مبدأ ياو مينيمكس [ 9 ] (حالة خاصة من نظرية فون نيومان مينيمكس ) على أن تعقيد الاتصال العشوائي لدالة ما يساوي تعقيدها التوزيعي الأقصى، حيث يتم أخذ الحد الأقصى على جميع التوزيعات المشتركة للمدخلات (ليس بالضرورة توزيعات المنتج!).

يمكن استخدام مبدأ ياو لإثبات حدود دنيا لتعقيد الاتصال العشوائي لدالة ما: صمم التوزيع المشترك المناسب، ثم أثبت حدًا أدنى لتعقيد التوزيع. ولأن تعقيد التوزيع يتعلق بالبروتوكولات الحتمية، فقد يكون هذا أسهل من إثبات حد أدنى للبروتوكولات العشوائية مباشرةً.

كمثال، دعونا ننظر إلى دالة الانفصال DISJ: يتم تفسير كل مدخل من المدخلات على أنه مجموعة جزئية من{1،...،ن}{\displaystyle \{1,\dots ,n\}}ويكون DISJ( x , y ) = 1 إذا كانت المجموعتان منفصلتين. وقد أثبت رازبوروف [ 10 ] ذلك.Ω(ن){\displaystyle \Omega (n)}الحد الأدنى لتعقيد الاتصال العشوائي من خلال النظر في التوزيع التالي: باحتمالية 3/4، يتم أخذ عينة من مجموعتين عشوائيتين منفصلتين بحجمن/4{\displaystyle n/4}وباحتمالية 1/4، قم بأخذ عينة من مجموعتين عشوائيتين بحجمن/4{\displaystyle n/4}مع تقاطع فريد.

تعقيد المعلومات

يُعدّ تعقيد المعلومات منهجًا قويًا لدراسة التعقيد التوزيعي. وقد بدأ هذا المنهج كلٌّ من بار يوسف، وجايرام، وكومار، وسيفاكومار، [ 11 ] وتمّ تقنينه في أعمال باراك، وبرافرمان، وتشين، وراو، [ 12 ] ، وكذلك من قِبل برافرمان وراو. [ 13 ]

يُعرَّف تعقيد المعلومات (الداخلي) لبروتوكول R (الذي قد يكون عشوائيًا) بالنسبة لتوزيع μ على النحو التالي.(X،Y)∼μ{\displaystyle (X,Y)\sim \mu }لنفترض أن المدخلات عشوائية تم أخذ عينات منها وفقًا لـ μ ، ولنفترض أن Π هي نسخة R عند تشغيلها على المدخلات.X،Y{\displaystyle X,Y}. تعقيد المعلومات في البروتوكول هو

ICμ⁡(R)=أنا(Π;Y|X)+أنا(Π;X|Y)،{\displaystyle \operatorname {IC} _{\mu }(R)=I(\Pi ;Y|X)+I(\Pi ;X|Y),}

حيث يشير I إلى المعلومات المتبادلة الشرطية . يقيس الحد الأول مقدار المعلومات التي تتعلمها أليس عن مدخلات بوب من النص، ويقيس الحد الثاني مقدار المعلومات التي يتعلمها بوب عن مدخلات أليس.

إن تعقيد المعلومات ε- خطأ للدالة f بالنسبة للتوزيع μ هو تعقيد المعلومات الأدنى لبروتوكول f الذي يكون خطأه (بالنسبة لـ μ ) على الأكثر ε .

أثبت برافرمان وراو أن المعلومات تساوي تكلفة الاتصال المُستهلكة. وهذا يعني أن تكلفة حلّ n نسخة مستقلة من f تُعادل تقريبًا n ضعف تعقيد المعلومات في f . وهذا يُشابه التفسير المعروف لإنتروبيا شانون باعتبارها طول البت المُستهلك اللازم لنقل البيانات من مصدر معلومات مُحدد. يستخدم برهان برافرمان وراو تقنية تُعرف باسم "ضغط البروتوكول"، حيث يتم "ضغط" بروتوكول ذي كفاءة معلوماتية عالية إلى بروتوكول ذي كفاءة اتصالية عالية.

تُمكّن تقنيات تعقيد المعلومات من حساب تعقيد الاتصال الدقيق (حتى الدرجة الأولى) لانفصال المجموعات.1.4923...ن{\displaystyle 1.4923\ldots n}[ 14 ]​

كما تم استخدام تقنيات تعقيد المعلومات لتحليل الصيغ الموسعة، مما أثبت وجود حد أدنى مثالي بشكل أساسي لتعقيد الخوارزميات القائمة على البرمجة الخطية التي تحل تقريبًا مشكلة الزمرة القصوى . [ 15 ]

يستعرض استطلاع عمري وينشتاين لعام 2015 [ 16 ] الموضوع.

تعقيد الاتصالات الكمومية

يحاول مفهوم تعقيد الاتصالات الكمومية تحديد مقدار تقليل الاتصالات الممكن باستخدام التأثيرات الكمومية أثناء عملية حسابية موزعة.

تم اقتراح ثلاثة تعميمات كمومية على الأقل لتعقيد الاتصال؛ للاطلاع على دراسة استقصائية، انظر النص المقترح من قبل جي. براسارد.

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

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

يتضمن النموذج الثالث الوصول إلى التشابك المشترك مسبقًا بالإضافة إلى اتصال الكيوبت ، وهو الأقل استكشافًا من بين النماذج الكمومية الثلاثة.

تعقيد الاتصال غير الحتمي

في سياق تعقيد الاتصالات غير الحتمية، تمتلك أليس وبوب وسيلة للوصول إلى وسيط روحي. بعد تلقي كلمة الوسيط، يتواصل الطرفان لاستنتاجو(x،y){\displaystyle f(x,y)}وبالتالي، يكون تعقيد الاتصال غير الحتمي هو الحد الأقصى لجميع الأزواج.(x،y){\displaystyle (x,y)}على مجموع عدد البتات المتبادلة وطول ترميز كلمة أوراكل.

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

يظهر تعقيد الاتصال غير الحتمي كوسيلة للحصول على حدود دنيا لتعقيد الاتصال الحتمي (انظر Dietzfelbinger et al.)، ولكن أيضًا في نظرية المصفوفات غير السالبة، حيث يعطي حدًا أدنى للرتبة غير السالبة لمصفوفة غير سالبة . [ 17 ]

تعقيد الاتصال غير المحدود بالأخطاء

في حالة الخطأ غير المحدود، يكون لدى أليس وبوب إمكانية الوصول إلى عملة خاصة ومدخلاتهما الخاصة.(x،y){\displaystyle (x,y)}في هذا السياق، تنجح أليس إذا أجابت بالقيمة الصحيحة لـو(x،y){\displaystyle f(x,y)}باحتمالية أكبر من 1/2. بعبارة أخرى، إذا كانت استجابات أليس مرتبطة بأي شكل من الأشكال بالقيمة الحقيقية لـو(x،y){\displaystyle f(x,y)}وعندها يُعتبر البروتوكول صالحاً.

لاحظ أن شرط سرية العملة أمر أساسي. على وجه الخصوص، إذا لم يتم احتساب عدد البتات العامة المشتركة بين أليس وبوب ضمن تعقيد الاتصال، فمن السهل القول إن حساب أي دالة لديهيا(1){\displaystyle O(1)}تعقيد الاتصال. [ 18 ] من ناحية أخرى، يكون كلا النموذجين متكافئين إذا تم احتساب عدد البتات العامة التي تستخدمها أليس وبوب ضمن إجمالي الاتصال في البروتوكول. [ 19 ]

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

كان فورستر [ 21 ] أول من أثبت حدودًا دنيا صريحة لهذه الفئة، موضحًا أن حساب الجداء الداخلي⟨x،y⟩{\displaystyle \langle x,y\rangle }يتطلب على الأقلΩ(ن){\displaystyle \Omega (n)}أجزاء من الاتصال، على الرغم من أن نتيجة سابقة لألون وفرانكل ورودل أثبتت أن تعقيد الاتصال لجميع الدوال المنطقية تقريبًاو:{0،1}ن×{0،1}ن→{0،1}{\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\to \{0,1\}}يكونΩ(ن){\displaystyle \Omega (n)}[ 22 ]​

رفع

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

تم تطوير هذه التقنية في سياق تعقيد الاتصال بواسطة راز وماكنزي، [ 23 ] الذين أثبتوا أول نظرية رفع الاستعلام إلى الاتصال، واستخدموا النتيجة لفصل التسلسل الهرمي NC الرتيب.

بالنظر إلى دالةو:{0،1}ن→{0،1}{\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}وجهازز:{0،1}أ×{0،1}ب→{0،1}{\displaystyle g\colon \{0,1\}^{a}\times \{0,1\}^{b}\to \{0,1\}}، تركيبهاو∘ز:{0،1}نأ×{0،1}نب→{0،1}{\displaystyle f\circ g\colon \{0,1\}^{na}\times \{0,1\}^{nb}\to \{0,1\}}يُعرَّف على النحو التالي:

(و∘ز)(x،y)=و(ز(x1،1⋯x1،أ،y1،1⋯y1،ب)،...،ز(xن،1⋯xن،أ،yن،1⋯yن،ب)).{\displaystyle (f\circ g)(x,y)=f(g(x_{1,1}\cdots x_{1,a},y_{1,1}\cdots y_{1,b}),\dots ,g(x_{n,1}\cdots x_{n,a},y_{n,1}\cdots y_{n,b})).}

بالكلمات،x{\displaystyle x}يتم تقسيمها إلىن{\displaystyle n}كتل من الطولأ{\displaystyle a}، وy{\displaystyle y}يتم تقسيمها إلىن{\displaystyle n}كتل من الطولب{\displaystyle b}يتم تطبيق الجهازن{\displaystyle n}يتم تحديد الأوقات على الكتل، ويتم تغذية المخرجات إلىو{\displaystyle f}. بشكل تخطيطي:

في هذا الرسم التخطيطي، كل مدخل من المدخلاتx1،...،xن{\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}يبلغ طوله بتات ، وكل مدخل من المدخلاتy1،...،yن{\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{n}}طوله b بت.

شجرة قرارات عميقةΔ{\displaystyle \Delta }لو{\displaystyle f}يمكن ترجمتها إلى بروتوكول اتصال تكلفتهΔ⋅د(ز){\displaystyle \Delta \cdot D(g)}في كل مرة يستعلم فيها الشجر عن جزء، تكون القيمة المقابلة لـز{\displaystyle g}يتم حسابها باستخدام بروتوكول أمثل لـز{\displaystyle g}أظهر راز وماكنزي أن هذا هو الأمثل حتى عامل ثابت عندماز{\displaystyle g}وهو ما يسمى "أداة الفهرسة"، والتيx{\displaystyle x}له طولجسجل⁡ن{\displaystyle c\log n}(لثابت c كبير بما فيه الكفاية )،y{\displaystyle y}له طولنج{\displaystyle n^{c}}، وز(x،y){\displaystyle g(x,y)}هوx{\displaystyle x}الجزء رقم -th منy{\displaystyle y}.

تعتمد برهان نظرية رفع راز-ماكنزي على طريقة المحاكاة، حيث يتم استخدام بروتوكول للدالة المركبةو∘ز{\displaystyle f\circ g}يُستخدم لإنشاء شجرة قرارات لـو{\displaystyle f}قدّم غوس، وبيتاسي، وواتسون [ 24 ] شرحًا للبرهان الأصلي. ومنذ ذلك الحين، أثبتت العديد من الدراسات نظريات مماثلة باستخدام أدوات مختلفة، مثل الضرب الداخلي. [ 25 ] أصغر أداة يمكن التعامل معها هي أداة الفهرسة معج=1+ϵ{\displaystyle c=1+\epsilon }[ 26 ] قام كل من غوس وبيتاسي وواتسون بتوسيع تقنية راز-ماكنزي لتشمل البروتوكولات العشوائية. [ 27 ]

يُعطي تعديل بسيط لنظرية رفع راز-ماكنزي حدًا أدنى لـΔ⋅د(ز){\displaystyle \Delta \cdot D(g)}على لوغاريتم حجم شجرة البروتوكول للحوسبةو∘ز{\displaystyle f\circ g}، أينΔ{\displaystyle \Delta }يمثل عمق شجرة القرار الأمثل لـو{\displaystyle f}قام كل من غارغ، وغوس، وكامث، وسوكولوف بتوسيع هذا المفهوم ليشمل إطارًا مشابهًا للرسم البياني الموجه غير الدوري (DAG) ، [ 28 ] واستخدموا نتائجهم للحصول على حدود دنيا رتيبة للدوائر . وقد أسفرت التقنية نفسها أيضًا عن تطبيقات في تعقيد البرهان . [ 29 ]

يُجسّد نوع مختلف من الرفع طريقة مصفوفة الأنماط لشيرستوف، [ 30 ] والتي تُعطي حدًا أدنى لتعقيد الاتصالات الكمومية.و∘ز{\displaystyle f\circ g}حيث g هي أداة فهرسة معدلة، وذلك بدلالة الدرجة التقريبية للدالة f . الدرجة التقريبية للدالة المنطقية هي الحد الأدنى لدرجة متعددة الحدود التي تقرب الدالة على جميع النقاط المنطقية حتى خطأ إضافي مقداره 1/3.

على عكس برهان راز-ماكنزي، الذي يستخدم طريقة المحاكاة، يأخذ برهان شيرستوف شاهدًا مزدوجًا على الدرجة التقريبية لـ f ويعطي حدًا أدنى لتعقيد الاستعلام الكمومي لـو∘ز{\displaystyle f\circ g}باستخدام طريقة التباين المعممة ، تُعتبر الشهادة الثنائية للدرجة التقريبية للدالة f شهادة حد أدنى للدرجة التقريبية المُستنتجة عبر ازدواجية البرمجة الخطية . تُدمج هذه الشهادة الثنائية في كائنات أخرى تُشكل بيانات لطريقة التباين المعممة.

ومن الأمثلة الأخرى على هذا النهج عمل بيتاسي وروبير [ 31 ] ، حيث تم رفع فجوة جبرية إلى حد أدنى لمقياس رتبة رازبوروف . والنتيجة هي حد أدنى أسي قوي لتعقيد الدائرة الرتيبة لدالة صريحة، تم الحصول عليه من خلال توصيف كارتشمر-ويجدرسون [ 32 ] لحجم الدائرة الرتيبة بدلالة تعقيد الاتصال.

المشكلات المفتوحة

بالنظر إلى مصفوفة إدخال 0 أو 1مو=[و(x،y)]x،y∈{0،1}ن{\displaystyle M_{f}=[f(x,y)]_{x,y\in \{0,1\}^{n}}}، وهو الحد الأدنى لعدد البتات المتبادلة لحسابو{\displaystyle f}بشكل حتمي في أسوأ الحالات،د(و){\displaystyle D(f)}من المعروف أن المصفوفة محدودة من الأسفل بلوغاريتم رتبة المصفوفةمو{\displaystyle M_{f}}تقترح فرضية رتبة السجل أن تعقيد الاتصال ،د(و){\displaystyle D(f)}، محدودة من الأعلى بقوة ثابتة للوغاريتم رتبةمو{\displaystyle M_{f}}بما أن D(f) محدودة من الأعلى والأسفل بكثيرات حدود من الرتبة اللوغاريتمية(مو){\displaystyle (M_{f})}يمكننا القول أن D(f) مرتبطٌ ارتباطًا متعدد الحدود بالرتبة اللوغاريتمية(مو){\displaystyle (M_{f})}بما أن رتبة المصفوفة قابلة للحساب في زمن متعدد الحدود بالنسبة لحجم المصفوفة، فإن هذا الحد الأعلى يسمح بتقريب تعقيد الاتصال للمصفوفة في زمن متعدد الحدود. مع ذلك، تجدر الإشارة إلى أن حجم المصفوفة نفسها يتناسب أُسّيًا مع حجم المدخلات.

بالنسبة للبروتوكول العشوائي، تم افتراض أن عدد البتات المتبادلة في أسوأ الحالات، R(f)، يرتبط ارتباطًا متعدد الحدود بالصيغة التالية:

سجل⁡مين(رتبة(مو′):مو′∈R2ن×2ن،(مو-مو′)∞≤1/3).{\displaystyle \log \min({\textrm {rank}}(M'_{f}):M'_{f}\in \mathbb {R} ^{2^{n}\times 2^{n}},(M_{f}-M'_{f})_{\infty }\leq 1/3).}

تُعدّ فرضيات رتبة اللوغاريتم هذه قيّمة لأنها تُختزل مسألة تعقيد الاتصال في المصفوفة إلى مسألة استقلال صفوف (أعمدة) المصفوفة خطيًا. وقد دُحضت هذه الصيغة تحديدًا، والتي تُسمى فرضية رتبة اللوغاريتم التقريبية، مؤخرًا من قِبل تشاتوبادياي، وماندي، وشريف (2019) [ 33 ] باستخدام مثال مضاد بسيط بشكلٍ مُثير للدهشة. ويكشف هذا أن جوهر مشكلة تعقيد الاتصال، كما في حالة المعادلة المذكورة أعلاه، هو تحديد موقع المُدخلات في المصفوفة، وذلك لمعرفة ما إذا كانت مُتكافئة.

التطبيقات

يمكن استخدام الحدود الدنيا في تعقيد الاتصالات لإثبات الحدود الدنيا في تعقيد شجرة القرار ، ودوائر VLSI ، وهياكل البيانات، وخوارزميات البث ، ومفاضلات المساحة والوقت لآلات تورينج ، وغير ذلك. [ 2 ]

درس كونيتزر وساندولم [ 34 ] تعقيد الاتصال لبعض قواعد التصويت الشائعة ، والتي تُعدّ أساسية في المنظمات السياسية وغير السياسية. ويُعدّ تعقيد التجميع مفهومًا وثيق الصلة، ويمكن اعتباره تعقيد اتصال لجولة واحدة.

قام نايبي [ 35 ] بدراسة تعقيد الاتصال بين البايزيين غير المحدودين والمحدودين، ووضع نظريات لا غداء مجاني (حدود دنيا) حول محاذاة الذكاء الاصطناعي .

انظر أيضاً

ملحوظات

  1. 1 2 ياو، أ.س. ( 1979)، "بعض مسائل التعقيد المتعلقة بالحوسبة الموزعة"، وقائع الندوة الحادية عشرة حول نظرية الحوسبة ، 14 : 209-213
  2. 1 2 كوشيليفيتز، إيال؛ نيسان، نوام (1997). تعقيد الاتصال . مطبعة جامعة كامبريدج. ISBN 978-0-521-56067-2.
  3. ↑ كليف، ريتشارد؛ فان دام، ويم؛ نيلسن، مايكل؛ تاب، آلان (1999). "التشابك الكمي وتعقيد الاتصال لدالة الضرب الداخلي" . الحوسبة الكمية والاتصالات الكمية . سلسلة محاضرات في علوم الحاسوب. المجلد 1509. الصفحات 61-74 . doi : 10.1007/3-540-49208-9_4 . ISBN   978-3-540-65514-5. OSTI 661703 . 
  4. ^ نافاسكويس، ميغيل. جوريانوفا، يلينا؛ هوبان، ماتي J.؛ أسين ، أنطونيو (2015). "الارتباطات الكمومية تقريبًا" . اتصالات الطبيعة . 6 6288. أرخايف : 1403.4621 . بيب كود : 2015NatCo...6.6288N . دوى : 10.1038/ncomms7288 . بميد 25697645 . 
  5. ↑ دبليو فان دام، اللامكانية وتعقيد الاتصال، أطروحة دكتوراه، جامعة أكسفورد (1999).
  6. ↑ براسارد، جيل؛ بورمان، هاري؛ ليندن، نوح؛ ميثوت، أندريه آلان؛ تاب، آلان؛ أونغر، فالك (27 يونيو 2006). "حدود اللا-محلية في أي عالم لا يكون فيه تعقيد الاتصال تافهاً". رسائل المراجعة الفيزيائية . 96 (25) 250401. arXiv : quant-ph/0508042 . Bibcode : 2006PhRvL..96y0401B . doi : 10.1103/PhysRevLett.96.250401 . PMID 16907289 . 
  7. ↑ برونر، نيكولاس؛ سكرزيبكزيك، بول (24 أبريل 2009). "تقطير اللا موضعية ونظريات ما بعد الكم ذات تعقيد الاتصال البسيط". رسائل المراجعة الفيزيائية . 102 (16) 160403. arXiv : 0901.4070 . Bibcode : 2009PhRvL.102p0403B . doi : 10.1103/PhysRevLett.102.160403 . PMID 19518687 . 
  8. ↑ بوتيرون، بيير؛ برودبنت، آن؛ برولكس، مارك-أوليفييه (14 فبراير 2024). "توسيع النطاق المعروف للمربعات غير المحلية التي تُقلل من تعقيد الاتصال". رسائل المراجعة الفيزيائية . 132 (7) 070201. arXiv : 2302.00488 . Bibcode : 2024PhRvL.132g0201B . doi : 10.1103/PhysRevLett.132.070201 . PMID 38427887 . 
  9. ↑ ياو، أندرو تشي-تشيه (1977). "الحسابات الاحتمالية: نحو مقياس موحد للتعقيد". الندوة السنوية الثامنة عشرة حول أسس علوم الحاسوب (SFCS 1977) . معهد مهندسي الكهرباء والإلكترونيات. doi : 10.1109/SFCS.1977.24 . ISSN 0272-5428 . 
  10. ↑ رازبوروف، ألكسندر (1992). "حول التعقيد التوزيعي للانفصال" . علوم الحاسوب النظرية . 106 (2): 385-390 . doi : 10.1016/0304-3975(92)90260-M .
  11. ↑ بار يوسف، زيف؛ جايرام، تي إس؛ كومار، رافي؛ سيفاكومار، د. (2004). "نهج إحصائي معلوماتي لتعقيد تدفق البيانات والاتصالات" (ملف PDF) . مجلة علوم الحاسوب والنظم . 68 (4): 702-732 . doi : 10.1016/j.jcss.2003.11.006 . تاريخ الاسترجاع: 1 ديسمبر 2023 .
  12. ↑ باراك، بواز ؛ برافرمان، مارك ؛ تشين، شي؛ راو، أنوب (2013). "كيفية ضغط الاتصالات التفاعلية" (ملف PDF) . مجلة SIAM للحوسبة . 42 (3): 1327-1363 . doi : 10.1137/100811969 .
  13. ↑ برافرمان، مارك ؛ راو، أنوب (2014). "المعلومات تساوي تكلفة الاتصال المُستهلكة". معاملات IEEE في نظرية المعلومات . 60 (10): 6058-6069 . arXiv : 1106.3595 . doi : 10.1109/TIT.2014.2347282 .
  14. ↑ برافرمان، مارك ؛ غارغ، أنكيت؛ بانكراتوف، دينيس؛ وينشتاين، عمري (يونيو 2013). STOC '13: وقائع الندوة السنوية الخامسة والأربعين لجمعية ACM حول نظرية الحوسبة . بالو ألتو، كاليفورنيا: ACM. الصفحات 151-160 . doi : 10.1145/2488608.2488628 . ISBN  978-1-4503-2029-0.
  15. ↑ برافرمان، مارك ؛ مويترا، أنكور (1 يونيو 2013). "نهج تعقيد المعلومات للصياغات الموسعة" . STOC '13: وقائع الندوة السنوية الخامسة والأربعين لجمعية ACM حول نظرية الحوسبة . بالو ألتو، كاليفورنيا: ACM. الصفحات 161-170 . doi : 10.1145/2488608.2488629 . 
  16. ↑ وينشتاين، عمري (يونيو 2015). "تعقيد المعلومات والسعي نحو الضغط التفاعلي" . أخبار ACM SIGACT . 46 (2): 41-64 . doi : 10.1145/2789149.2789161 . تاريخ الاسترجاع: 1 ديسمبر 2023 .
  17. ↑ ياناكاكيس، م. (1991). "التعبير عن مسائل التحسين التوافقي بواسطة البرامج الخطية". مجلة علوم الحاسوب والأنظمة . 43 (3): 441-466 . doi : 10.1016/0022-0000(91)90024-y .
  18. ↑ لوفيت، شاشار، CSE 291: تعقيد الاتصالات، شتاء 2019، بروتوكولات الأخطاء غير المحدودة (ملف PDF) ، تم الاطلاع عليه في 9 يونيو 2019
  19. ↑ غوس، ميكا؛ بيتاسي، تونيان؛ واتسون، توماس (2018-06-01). "مشهد فئات تعقيد الاتصال" . التعقيد الحسابي . 27 (2): 245-304 . doi : 10.1007/s00037-018-0166-6 . ISSN 1420-8954 . S2CID 4333231 .  
  20. ↑ شيرستوف، ألكسندر أ. (أكتوبر 2008). "تعقيد الاتصال غير المحدود للدوال المتناظرة". المؤتمر السنوي التاسع والأربعون لمعهد مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب ، 2008. الصفحات 384-393 . doi : 10.1109/focs.2008.20 . ISBN  978-0-7695-3436-7. S2CID 9072527 . 
  21. ↑ فورستر، يورغن (2002). "حد أدنى خطي لتعقيد الاتصال الاحتمالي للخطأ غير المحدود" . مجلة علوم الحاسوب والنظم . 65 (4): 612-625 . doi : 10.1016/S0022-0000(02)00019-3 .
  22. ↑ ألون، ن .؛ فرانكل، ب.؛ رودل، ف. (أكتوبر 1985). "التحقيق الهندسي لأنظمة المجموعات وتعقيد الاتصال الاحتمالي". الندوة السنوية السادسة والعشرون حول أسس علوم الحاسوب (SFCS 1985) . بورتلاند، أوريغون، الولايات المتحدة الأمريكية: IEEE. الصفحات 277-280 . CiteSeerX 10.1.1.300.9711 . doi : 10.1109/SFCS.1985.30 . ISBN   9780818606441. S2CID 8416636 . 
  23. ↑ راز، ران ؛ ماكنزي، بيير (1999). "فصل التسلسل الهرمي للوحدات غير العددية الرتيبة". كومبيناتوريكا . 19 (3): 403-435 . doi : 10.1007/s004930050062 .
  24. ↑ غوس، ميكا؛ بيتاسي، تونيان ؛ واتسون، توماس (2018). "الاتصال الحتمي مقابل عدد الأقسام" . مجلة SIAM للحوسبة . 74 (6): 2435-2450 . doi : 10.1137/16M1059369 .
  25. ↑ تشاتوبادياي، أركاديف؛ كوتشكي، ميشال؛ لوف، برونو؛ موخوبادياي، ساغنيك (2019). "نظريات المحاكاة عبر خصائص شبه عشوائية" . التعقيد الحسابي . 28 (4): 617-659 . arXiv : 1704.06807 . doi : 10.1007/s00037-019-00190-7 .
  26. ↑ لوفيت، شاشار؛ ميكا، راغو؛ ميرتز، إيان؛ بيتاسي، تونيان ؛ تشانغ، جيا بينغ (200). "الرفع باستخدام عباد الشمس" (ملف PDF) . المؤتمر الثالث عشر للابتكارات في علوم الحاسوب النظرية (ITCS 2022) . المجلد 215. وقائع لايبنيز الدولية في المعلوماتية (LIPIcs). الصفحات 104:1–104:24. doi : 10.4230/LIPIcs.ITCS.2022.104 .  
  27. ↑ غوس، ميكا؛ بيتاسي، تونيان ؛ واتسون، توماس (2017). "رفع مستوى الاستعلام إلى مستوى الاتصال لـ BPP". المؤتمر السنوي الثامن والخمسون لمؤسسة IEEE حول أسس علوم الحاسوب (FOCS) لعام 2017. بيركلي، كاليفورنيا: IEEE. arXiv : 1703.07666 . doi : 10.1109/FOCS.2017.21 .
  28. ↑ غارغ، أنكيت؛ غوس، ميكا؛ كاماث، بريتيش؛ سوكولوف، ديمتري (2020). "الحدود الدنيا للدوائر الرتيبة من خلال التحليل" . نظرية الحوسبة . 16 : 13:1–13:30. doi : 10.4086/toc.2020.v016a013 .
  29. ↑ دي ريزيندي، سوزانا؛ مير، أور؛ نوردستروم، جاكوب؛ بيتاسي، تونيان ؛ روبير، روبير؛ فينيالز، مارك (2020). "الرفع باستخدام أدوات بسيطة وتطبيقاتها على تعقيد الدوائر والبرهان". المؤتمر السنوي الحادي والستون لمؤسسة مهندسي الكهرباء والإلكترونيات (IEEE) حول أسس علوم الحاسوب (FOCS) لعام 2020. مؤتمر افتراضي: IEEE. الصفحات 24-30 . arXiv : 2001.02144 . doi : 10.1109/FOCS46700.2020.00011 . 
  30. ↑ شيرستوف، ألكسندر (2011). "طريقة مصفوفة الأنماط". مجلة SIAM للحوسبة . 40 (6): 1969-2000 . arXiv : 0906.4291 . doi : 10.1137/080733644 .
  31. ↑ بيتاسي، تونيان ؛ روبير، روبرت (2017). "حدود دنيا أسية قوية للحساب الرتيب" (ملف PDF) . STOC 2017: وقائع الندوة السنوية التاسعة والأربعين لجمعية ACM SIGACT حول نظرية الحوسبة . مونتريال: ACM. الصفحات 1246-1255 . doi : 10.1145/3055399.3055478 . 
  32. ↑ كارتشمر، ماوريسيو؛ ويغدرسون، آفي (1990). "الدوائر الرتيبة للاتصال تتطلب عمقًا فوق لوغاريتمي" (ملف PDF) . مجلة SIAM للرياضيات المتقطعة . 3 (2): 255-265 . doi : 10.1137/0403021 .
  33. ↑ تشاتوبادياي، أركاديف؛ ماندي، نيخيل س.؛ شريف، سهيل (2019). "فرضية الرتبة التقريبية اللوغاريتمية خاطئة". 2019، وقائع الندوة السنوية الحادية والخمسين لجمعية الحوسبة الآلية حول نظرية الحوسبة: 42-53. https://doi.org/10.1145/3313276.3316353
  34. ↑ كونيتزر، فينسنت؛ ساندولم، توماس (5 يونيو 2005). "تعقيد الاتصال لقواعد التصويت الشائعة" . وقائع المؤتمر السادس لجمعية آلات الحوسبة حول التجارة الإلكترونية . EC '05. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 78-87 . doi : 10.1145/1064009.1064018 . ISBN  978-1-59593-049-1.
  35. ↑ نايبي، آران (2025). "العوائق الجوهرية والمسارات العملية لمواءمة الإنسان والذكاء الاصطناعي: تحليل التعقيد القائم على الاتفاق". arXiv : 2502.05934 [ cs.AI ].سيتم عرضها في المؤتمر الأربعين لجمعية النهوض بالذكاء الاصطناعي (AAAI 2026)، المسار الخاص بمواءمة الذكاء الاصطناعي (شفوي).

مراجع

  • راو، أنوب؛ يهودايوف، أمير (2020). تعقيد الاتصالات وتطبيقاتها . كامبريدج: مطبعة جامعة كامبريدج. ISBN 9781108671644.
  • كوشيليفيتز، إيال؛ نيسان، نوام (2006). تعقيد الاتصال . كامبريدج: مطبعة جامعة كامبريدج. ISBN 978-0-521-02983-4. OCLC 70764786 . 
  • براسارد، ج. تعقيد الاتصالات الكمومية: دراسة استقصائية. https://arxiv.org/abs/quant-ph/0101005
  • Dietzfelbinger, M., J. Hromkovic, J., and G. Schnitger, " مقارنة بين طريقتين للحد الأدنى لتعقيد الاتصال "، Theoret. Comput. Sci. 168, 1996. 39–51.
  • راز، ران . "تعقيد الدوائر والاتصالات". في نظرية التعقيد الحسابي. ستيفن روديتش وآفي ويغدرسون، محرران. معهد الجمعية الرياضية الأمريكية للدراسات المتقدمة، 2004. 129-137.
  • ياو، "بعض مسائل التعقيد المتعلقة بالحوسبة الموزعة"، وقائع المؤتمر الحادي عشر لنظرية الحوسبة، الصفحات  209-213، 1979. 14
  • I. Newman, Private vs. Common Random Bits in Communication Complexity , Information Processing Letters 39, 1991, pp.  67–71.