نظرية الحساسية

في مجال التعقيد الحسابي ، تنص نظرية الحساسية ، التي أثبتها هاو هوانغ في عام 2019، ^{[ 1 ]} على أن حساسية الدالة المنطقية${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$وهو على الأقل الجذر التربيعي لدرجته ، وبذلك حسمت فرضية طرحها نيسان وسيجيدي في عام 1992. ^{[ 2 ]} ويُعدّ البرهان موجزًا ​​بشكل ملحوظ، نظرًا لأن التقدم السابق كان محدودًا. ^{[ 3 ]}

أظهرت العديد من الأبحاث في أواخر الثمانينيات وأوائل التسعينيات ^{[ 4 ] [ 5 ] [ 6 ] [ 7 ]} أن مقاييس تعقيد شجرة القرار المختلفة للدوال المنطقية مرتبطة ارتباطًا متعدد الحدود، مما يعني أنه إذا${\displaystyle \alpha (f),\beta (f)}$ثم هناك اثنان من هذه التدابير${\displaystyle \alpha (f)\leq C\beta (f)^{C}}$لبعض الثوابت${\displaystyle C>0}$أظهر نيسان وسيجيدي ^{[ 2 ]} أن الدرجة والدرجة التقريبية ترتبطان أيضًا ارتباطًا متعدد الحدود بجميع هذه المقاييس. وقد استند برهانهما إلى مقياس تعقيد آخر، وهو حساسية الكتلة ، الذي قدمه نيسان ^{[ 7 ]} . تُعمم حساسية الكتلة مقياسًا أكثر طبيعية، وهو الحساسية (الحرجة)، الذي ظهر سابقًا ^{[ 8 ] [ 9 ] [ 10 ].}

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

على مر السنين، تم إثبات العديد من الحالات الخاصة لفرضية الحساسية. ^{[ 14 ] [ 15 ]} وقد تم إثبات نظرية الحساسية بالكامل أخيرًا بواسطة هوانغ، ^{[ 1 ]} باستخدام اختزال غوتسمان ولينيال. ^{[ 16 ]}

كل دالة منطقية${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$يمكن التعبير عنها بطريقة فريدة كمتعددة حدود خطية . درجة${\displaystyle f}$هي درجة هذه المعادلة متعددة الحدود الفريدة، ويرمز لها بـ${\displaystyle \deg(f)}$.

حساسية الدالة البوليانية${\displaystyle f}$عند النقطة${\displaystyle x\in \{0,1\}^{n}}$عدد المؤشرات${\displaystyle i\in [n]}$بحيث${\displaystyle f(x^{\oplus i})\neq f(x)}$، أين${\displaystyle x^{\oplus i}}$يتم الحصول عليها من${\displaystyle x}$عن طريق قلب${\displaystyle i}$الإحداثي رقم 'th. حساسية${\displaystyle f}$هي أقصى حساسية لـ${\displaystyle f}$في أي وقت${\displaystyle x\in \{0,1\}^{n}}$، المشار إليه${\displaystyle s(f)}$.

تنص نظرية الحساسية على أن

${\displaystyle s(f)\geq {\sqrt {\deg(f)}}.}$

وفي الاتجاه الآخر، أظهر تال ^{[ 17 ]،} الذي حسّن حدًا سابقًا لنيسان وسيجيدي ^{[ 2 ]،} أن

${\displaystyle s(f)\leq \deg(f)^{2}.}$

تُعتبر نظرية الحساسية محكمة بالنسبة لدالة AND-of-OR: ^{[ 18 ]}

${\displaystyle \bigwedge _{i=1}^{m}\bigvee _{j=1}^{m}x_{ij}}$

لهذه الدالة درجة${\displaystyle m^{2}}$والحساسية${\displaystyle m}$.

يترك${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$لتكن دالة منطقية من الدرجة${\displaystyle d}$ضع في اعتبارك أي حد أقصى من${\displaystyle f}$أي، حد أحادي من الدرجة${\displaystyle d}$في متعددة الحدود الخطية الفريدة التي تمثل${\displaystyle f}$إذا استبدلنا قيمة عشوائية في الإحداثيات غير المذكورة في الحدّ، فسنحصل على دالة.${\displaystyle F}$على${\displaystyle d}$الإحداثيات التي لها درجة${\displaystyle d}$وعلاوة على ذلك،${\displaystyle s(f)\geq s(F)}$إذا أثبتنا نظرية الحساسية لـ${\displaystyle F}$ثم يتبع ذلك لـ${\displaystyle f}$لذا، من الآن فصاعدًا، نفترض دون فقدان للعمومية أن${\displaystyle f}$حاصل على درجة علمية${\displaystyle n}$.

قم بتعريف دالة جديدة${\displaystyle g\colon \{0,1\}^{n}\to \{0,1\}}$بواسطة

${\displaystyle g(x_{1},\dots ,x_{n})=f\oplus x_{1}\oplus \cdots \oplus x_{n}.}$

يمكن إثبات ذلك بما أن${\displaystyle f}$حاصل على درجة علمية${\displaystyle n}$ثم${\displaystyle g}$غير متوازن (بمعنى أن${\displaystyle |g^{-1}(0)|\neq |g^{-1}(1)|}$)، يقول${\displaystyle |g^{-1}(1)|>2^{n-1}}$ضع في اعتبارك الرسم البياني الفرعي${\displaystyle G}$من المكعب الفائق (الرسم البياني على${\displaystyle \{0,1\}^{n}}$حيث يكون رأسان متصلين إذا اختلفا بإحداثي واحد) ناتج عن${\displaystyle S=g^{-1}(1)}$لإثبات نظرية الحساسية، يكفي أن نُبين أن${\displaystyle G}$يحتوي على رأس درجته على الأقل${\displaystyle {\sqrt {n}}}$ويعود هذا الانخفاض إلى غوتسمان ولينيال. ^{[ 16 ]}

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

يترك${\displaystyle A}$لتكن مصفوفة التجاور الموقعة الموافقة للإشارة. الخاصية التي تنص على أن حاصل ضرب الإشارات في كل مربع هو${\displaystyle -1}$يشير ذلك إلى أن${\displaystyle A^{2}=nI}$وبالتالي نصف القيم الذاتية لـ${\displaystyle A}$نكون${\displaystyle {\sqrt {n}}}$ونصفهم${\displaystyle -{\sqrt {n}}}$. على وجه الخصوص، الفضاء الذاتي لـ${\displaystyle {\sqrt {n}}}$(الذي له أبعاد)${\displaystyle 2^{n-1}}$) يتقاطع مع فضاء المتجهات التي يدعمها${\displaystyle S}$(الذي له أبعاد)${\displaystyle >2^{n-1}}$)، مما يعني وجود متجه ذاتي${\displaystyle v}$ل${\displaystyle A}$مع القيمة الذاتية${\displaystyle {\sqrt {n}}}$وهو مدعوم على${\displaystyle S}$(هذا تبسيط لحجة هوانغ الأصلية التي قدمها شاليف بن ديفيد. ^{[ 20 ]} )

لنفترض نقطة${\displaystyle x\in S}$تعظيم${\displaystyle |v_{x}|}$. من ناحية،${\displaystyle Av={\sqrt {n}}v}$. على الجانب الآخر،${\displaystyle Av}$هو على الأكثر مجموع القيم المطلقة لجميع جيران${\displaystyle x}$في${\displaystyle S}$وهو على الأكثر${\displaystyle \deg _{G}(x)\cdot |v_{x}|}$. لذلك${\displaystyle \deg _{G}(x)\geq {\sqrt {n}}}$.

يمكن إعادة صياغة نظرية الحساسية بشكل مكافئ على النحو التالي:

${\displaystyle \deg(f)\leq s(f)^{2}.}$

قام لابلانت وآخرون ^{[ 21 ]} بتحسين هذا إلى

${\displaystyle \deg(f)\leq s_{0}(f)s_{1}(f),}$

أين${\displaystyle s_{b}(f)}$هي أقصى حساسية لـ${\displaystyle f}$في مرحلة ما${\displaystyle f^{-1}(b)}$وأظهروا كذلك أن هذا الحد يتم تحقيقه عند نقطتين متجاورتين من المكعب الفائق.

قام كل من آرونسون، وبن ديفيد، وكوثاري، وراو، وتال ^{[ 22 ]} بتعريف مقياس جديد، وهو الحساسية الطيفية لـ${\displaystyle f}$، المشار إليه${\displaystyle \lambda (f)}$هذه هي أكبر قيمة ذاتية لمصفوفة التجاور الخاصة بمخطط الحساسية لـ${\displaystyle f}$، وهو الرسم البياني الفرعي للمكعب الفائق الذي يتكون من جميع الحواف الحساسة (الحواف التي تربط نقطتين).${\displaystyle x,y}$بحيث${\displaystyle f(x)\neq f(y)}$). لقد أظهروا أن برهان هوانغ يمكن تقسيمه إلى خطوتين:

• ${\displaystyle \deg(f)\leq \lambda (f)^{2}}$.
• ${\displaystyle \lambda (f)\leq s(f)}$.

باستخدام هذا المقياس، أثبتوا العديد من العلاقات الوثيقة بين مقاييس تعقيد الدوال المنطقية:${\displaystyle \deg(f)=O(Q(f)^{2})}$و${\displaystyle D(f)=O(Q(f)^{4})}$. هنا${\displaystyle D(f)}$هل تعقيد الاستعلام الحتمي و${\displaystyle Q(f)}$هو تعقيد الاستعلام الكمي.

قام دافني وآخرون ^{[ 23 ]} بتوسيع مفهومي الدرجة والحساسية ليشملا الدوال البولية على المجموعة المتناظرة وعلى مخطط التطابق التام ، وأثبتوا نظائر لنظرية الحساسية لهذه الدوال. وتعتمد براهينهم على اختزال لنظرية حساسية هوانغ.

• نموذج شجرة القرار

• آرونسون، سكوت؛ بن ديفيد، شاليف؛ كوثاري، روبن؛ راو، شرافاس؛ تال، أفيشاي (15 يونيو 2021). الدرجة مقابل الدرجة التقريبية والآثار الكمومية لنظرية حساسية هوانغ . ACM. الصفحات 1330-1342 . arXiv : 2010.12629 . doi : 10.1145/3406325.3451047 . ISBN  978-1-4503-8053-9.
• الأحمدي، بهمن؛ الينغيبور، فاطمة؛ كافيرز، مايكل س. فلات، شون. ماجر، كارين. ناصرعصر، شهلا (سبتمبر 2013). “الحد الأدنى لعدد القيم الذاتية المميزة للرسوم البيانية”. المجلة الإلكترونية للجبر الخطي . 26 . جمعية الجبر الخطي الدولية: 673-691 . أرخايف : 1304.1205 . دوى : 10.13001/1081-3810.1679 . ردمك 1081-3810 . 
• بافنا، ميتالي؛ لوكام، ساتيانارايانا ف.؛ تافيناس، سيباستيان؛ فيلينجكر، أميا؛ فاليزيفسكي، بيوتر؛ موشول، أنكا؛ نيدرماير، رولف (2016). “حول تخمين الحساسية لصيغ القراءة k ”. الندوة الدولية الحادية والأربعون حول الأسس الرياضية لعلوم الكمبيوتر (MFCS 2016) . ص.  14 صفحة. دوى : 10.4230/LIPICS.MFCS.2016.16 . ردمك 1868-8969 . 
• دافني، نيتا؛ فيلموس، يوفال؛ ليفشيتز، نوام؛ ليندزي، ناثان؛ فينيالز، مارك؛ لي، جيمس ر. (2021). "مقاييس التعقيد على المجموعة المتناظرة وما بعدها (ملخص موسع)". المؤتمر الثاني عشر للابتكارات في علوم الحاسوب النظرية (ITCS) .  5 صفحات، 326343 بايت. doi : 10.4230/LIPICS.ITCS.2021.87 . ISSN 1868-8969 . 
• بن ديفيد، شاليف (3 يوليو 2019). "تم حل التعليق رقم 35 على تخمين الحساسية" .
• بلوم، مانويل؛ إمباغليازو، راسل (1987). "الأوراكل العامة وفئات الأوراكل". المؤتمر السنوي الثامن والعشرون حول أسس علوم الحاسوب (sfcs 1987) . معهد مهندسي الكهرباء والإلكترونيات. doi : 10.1109/sfcs.1987.30 .
• بورمان، هاري؛ دي وولف، رونالد (2002). "مقاييس التعقيد وتعقيد شجرة القرار: دراسة استقصائية". علوم الحاسوب النظرية . 288 (1). إلسيفير بي في: 21-43 . doi : 10.1016/s0304-3975(01)00144-x . ISSN 0304-3975 . 
• سي إس، كارثيك؛ تافيناس، سيباستيان؛ لال، أكاش؛ أكشاي، إس.؛ سوراب، ساكيت؛ سين، سانديب (2016). "حول فرضية الحساسية للأشكال الطبيعية المنفصلة". المؤتمر السنوي السادس والثلاثون للجمعية الدولية لأبحاث علوم الحاسوب حول أسس تكنولوجيا البرمجيات وعلوم الحاسوب النظرية (FSTTCS 2016) .  15 صفحة. doi : 10.4230/LIPICS.FSTTCS.2016.15 . ISSN 1868-8969 . 
• كوك، ستيفن؛ دورك، سينثيا؛ رايشوك، روديجر (1986). "الحدود الزمنية العليا والدنيا لآلات الوصول العشوائي المتوازية بدون عمليات كتابة متزامنة". مجلة SIAM للحوسبة . 15 (1): 87-97 . doi : 10.1137/0215006 . ISSN 0097-5397 . 
• غوتسمان، حاييم؛ لينال، ناتي (1992). "تكافؤ مسألتين على المكعب" . مجلة نظرية التوافيق، السلسلة أ . 61 (1). إلسيفير بي في: 142-146 . doi : 10.1016/0097-3165(92)90060-8 . ISSN 0097-3165 . 
• هارتمانيس، جوريس؛ هيماشاندرا، لين أ. (1991). "الدوال أحادية الاتجاه وعدم تماثل المجموعات الكاملة من فئة NP" . علوم الحاسوب النظرية . 81 (1): 155-163 . doi : 10.1016/0304-3975(91)90323-T .
• حاتمي، بويا؛ كولكارني، راغاف؛ بانكراتوف ، دينيس (2011). "الاختلافات في تخمين الحساسية" . نظرية الحوسبة . 1 (1): 1– 27. دوى : 10.4086/toc.gs.2011.004 . ردمك 1557-2862 . 
• هوانغ، هاو (2019-11-01). "الرسوم البيانية الفرعية المستحثة للمكعبات الفائقة وبرهان تخمين الحساسية". حوليات الرياضيات . 190 (3). arXiv : 1907.00847 . doi : 10.4007/annals.2019.190.3.6 . ISSN 0003-486X . 
• كلاريش، إريكا (25 يوليو 2019). "حل معضلة علوم الحاسوب التي تعود لعقود مضت في صفحتين" . مجلة كوانتا .
• لابلانت، صوفي؛ ناصر عسر، رضا؛ ساني، أنوبا؛ وانغ، تشونينغشين (2023-03-07). "تخمين الحساسية والمكعبات الفائقة الموقعة" . أرشيف HAL ​​المفتوح . تم الاسترجاع في 25 أبريل 2024 .
• نيسان، نوام (1991). "مخططات CREW PRAMs وأشجار القرار". مجلة SIAM للحوسبة . 20 (6): 999-1007 . doi : 10.1137/0220062 . ISSN 0097-5397 . 
• نيسان، نوام؛ سيجيدي، ماريو (1994). "حول درجة الدوال البوليانية كمتعددات حدود حقيقية". التعقيد الحسابي . 4 (4): 301-313 . doi : 10.1007/BF01263419 . ISSN 1016-3328 . 
• سايمون، هانز-أولريش (1983). "حدٌّ دقيقٌ من Ω(loglog n) للوقت اللازم لحساب الدوال المنطقية غير المنحلة باستخدام ذاكرة الوصول العشوائي المتوازية". أسس نظرية الحوسبة . سلسلة محاضرات في علوم الحاسوب. المجلد  158. برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ. الصفحات 439-444 . doi : 10.1007/3-540-12689-9_124 . ISBN  978-3-540-12689-8.
• تال، أفيشاي (9 يناير 2013). "خصائص وتطبيقات تركيب الدوال المنطقية". وقائع المؤتمر الرابع حول الابتكارات في علوم الحاسوب النظرية (ITCS '13) . ACM. doi : 10.1145/2422436.2422485 . ISBN 978-1-4503-1859-4.
• تاردوس، ج. (1989). "تعقيد الاستعلام، أو لماذا يصعب فصله${\displaystyle NP^{A}\cap coNP^{A}}$من${\displaystyle P^{A}}$بواسطة أوراكل عشوائي${\displaystyle A}$". Combinatorica . 9 (4): 385–392 . doi : 10.1007/BF02125350 . ISSN 0209-9683 . 
• فيجنر، إنجو (1987). تعقيد الدوال البوليانية . شتوتغارت، تشيتشستر، نيويورك، بريسبان [وغيرها]: جون وايلي وأولاده. ISBN 0-471-91555-6.