مسألة مجموع الجذر التربيعي

مسألة مجموع الجذور التربيعية (SRS) هي مسألة حسابية لاتخاذ القرارات من مجال التحليل العددي ، ولها تطبيقات في الهندسة الحسابية . طُرحت هذه المسألة في عام 1981، ^{[ 1 ]} وربما قبل ذلك.

يتم تعريف SRS على النحو التالي: ^{[ 2 ]}

بفرض الأعداد الصحيحة الموجبة${\displaystyle a_{1},\ldots ,a_{k}}$و t عدد صحيح ، قرر ما إذا${\displaystyle \sum _{i=1}^{k}{\sqrt {a_{i}}}\leq t}$.

التعريف البديل هو:

بفرض الأعداد الصحيحة الموجبة${\displaystyle a_{1},\ldots ,a_{k}}$و${\displaystyle b_{1},\ldots ,b_{k}}$قرر ما إذا${\displaystyle \sum _{i=1}^{k}{\sqrt {a_{i}}}\leq \sum _{i=1}^{k}{\sqrt {b_{i}}}}$.

يمكن حل مسألة SRS في وقت متعدد الحدود في نموذج ذاكرة الوصول العشوائي الحقيقية . ^{[ 3 ]} مع ذلك، فإن تعقيد وقت تشغيلها في نموذج آلة تورينج لا يزال غير معروف حتى عام 1997. ^{[ 2 ]} تكمن الصعوبة الرئيسية في أنه لحل المسألة، يجب حساب الجذور التربيعية بدقة عالية، وهو ما قد يتطلب عددًا كبيرًا من البتات. وقد ذُكرت هذه المسألة في قسم "حديقة المسائل المفتوحة". ^{[ 4 ]}

يقدم بلومر ^{[ 5 ]} خوارزمية مونت كارلو ذات زمن متعدد الحدود لتحديد ما إذا كان مجموع الجذور التربيعية يساوي صفرًا. وتنطبق الخوارزمية بشكل أعم على أي مجموع للجذور .

أثبت أليندر، وبورجيسر، وبيدرسن، وميلترسن ^{[ 6 ]} أن SRS يقع في التسلسل الهرمي للعد (الموجود في PSPACE ). وعلى وجه التحديد، أظهروا أن SRS يقع في P ^{PP PP PP} ، في المستوى الرابع من التسلسل الهرمي للعد.

تتميز نسخة من المسألة، حيث تُعطى الجذور التربيعية بصيغة أحادية، بتعقيد أقل بكثير، من فئة P/poly . وهذا يعني أنه يمكن حلها باستخدام دوائر ذات حجم متعدد الحدود، على الرغم من أنه قد لا يكون من السهل إيجاد هذه الدوائر. ^{[ 7 ]}

إحدى طرق حل مشكلة SRS هي إثبات حد أدنى للفرق المطلق${\displaystyle \left|t-\sum _{i=1}^{k}{\sqrt {a_{i}}}\right|}$أو$\displaystyle \left|\sum _{i=1}^{k}{\sqrt {a_{i}}}-\sum _{i=1}^{k}{\sqrt {b_{i}}}\right|}$يُطلق على هذا الحد الأدنى اسم "حد الفصل" لأنه يفصل بين الفرق والصفر. على سبيل المثال، إذا كان الفرق المطلق على الأقل 2 ^{− d} ، فهذا يعني أنه يمكننا تقريب جميع الأرقام إلى d بت من الدقة، وحل SRS في وقت متعدد الحدود في d .

يؤدي هذا إلى المسألة الرياضية المتمثلة في إثبات حدود هذا الفرق. لنُعرّف r ( n , k ) على أنه أصغر قيمة موجبة للفرق.${\displaystyle \sum _{i=1}^{k}{\sqrt {a_{i}}}-\sum _{i=1}^{k}{\sqrt {b_{i}}}}$حيث aᵢ و _bᵢ عددان صحيحان بين 1 و n ؛ يُعرَّف R ( n , k ) على أنه -log r ( n , k )، وهو عدد أرقام الدقة المطلوبة لحل SRS. يُعد حساب r ( n , k ) المسألة المفتوحة _رقم 33 في مشروع المسائل المفتوحة ^{. [ 8} ]

على وجه الخصوص، من المثير للاهتمام معرفة ما إذا كانت قيمة r( n , k ) تقع ضمن نطاق O(poly( k , log( n ))). الإجابة الإيجابية تعني إمكانية حل مشكلة SRS في زمن متعدد الحدود باستخدام نموذج آلة تورينج. بعض الحدود المعروفة حاليًا هي:

• أثبت تشيان ووانغ ^{[ 9 ]} من خلال بناء صريح أنه لأي k و n ، ${\displaystyle r(n,k)\in O(n^{-2k+3/2})}$، لذا${\displaystyle R(n,k)\geq (2k-3/2)\cdot \log {n}}$هذا الرقم هو الأمثل لـ k = 2، وكذلك لمجموعة واسعة من الأعداد الصحيحة.
• أثبت كل من بيرنيكل وفليشر وميلورن وشيرا ^{[ 10 ]} حدًا أعلى لعدد الأرقام:${\displaystyle R(n,k)\in O(2^{2k}\cdot \log {n})}$.
• أظهر كل من تشنغ، ومينغ، وسون، وتشن ^{[ 11 ] أن}${\displaystyle R(n,k)\in 2^{O(n/\log {n})}\cdot \log {n}}$.
• أظهر تشنغ ولي ^{[ 12 ] أن}${\displaystyle R(n,k)\in 2^{O(n/\log {n})}}$وهذا يعني أنه يمكن حل SRS في وقت${\displaystyle 2^{o(k)}\cdot (\log {n})^{O(1)}}$طالما أن n ينتمي إلى O( k log k ). كما يقدمون خوارزمية لحساب r ( n , k ) في زمن${\displaystyle n^{k+o(k)}}$.
• أثبت كل من أيزنبراند، وهايبرلي، وسينغر ^{[ 13 ] أن}${\displaystyle r(n,k)\geq \gamma \cdot n^{-2n}}$حيث أن غاما ثابت يعتمد على المدخلات a1 _، ...، an _، والخطوات من نظرية الفضاء الجزئي . وهذا يحسن الحد السابق${\displaystyle r(n,k)\geq \left(n\cdot \max _{i}({\sqrt {a_{i}}})\right)^{-2^{n}}}$.

تعتبر SRS مهمة في الهندسة الحسابية ، حيث يتم إعطاء المسافات الإقليدية بواسطة الجذور التربيعية، وتتطلب العديد من المسائل الهندسية (مثل الشجرة الممتدة الدنيا في المستوى ومسألة البائع المتجول الإقليدية ) حساب مجاميع المسافات.

يُظهر إيتيسامي وياناكاكيس ^{[ 14 ]} اختزالًا من SRS إلى مشكلة إنهاء الألعاب العشوائية المتزامنة المتكررة .

تتمتع SRS أيضًا بأهمية نظرية، لأنها حالة خاصة بسيطة من مشكلة جدوى البرمجة شبه المحددة . لننظر إلى المصفوفة${\displaystyle \left({\begin{matrix}1&x\\x&a\end{matrix}}\right)}$تكون هذه المصفوفة شبه موجبة إذا وفقط إذا${\displaystyle ax^{2}\geq 0}$، إذا${\displaystyle |x|\leq {\sqrt {a}}}$لذا، لحل مشكلة SRS، يمكننا بناء مسألة جدوى تتضمن n من القيود على النحو التالي :${\displaystyle \left({\begin{matrix}1&x_{i}\\x_{i}&a_{i}\end{matrix}}\right)\succeq 0}$وقيود خطية إضافية${\displaystyle x_{i}\geq 0,\sum _{i=1}^{n}x_{i}\geq k}$تكون البرمجة شبه المحددة الناتجة قابلة للتنفيذ إذا وفقط إذا كانت البرمجة شبه المحددة قابلة للتنفيذ. وبما أن تعقيد وقت تشغيل البرمجة شبه المحددة في نموذج آلة تورينج غير محدد، فإن الأمر نفسه ينطبق على قابلية تنفيذ البرمجة شبه المحددة (حتى عام 1997).

قام كايال وسها ^{[ 15 ]} بتوسيع نطاق المشكلة من الأعداد الصحيحة إلى كثيرات الحدود . وتشير نتائجهم إلى وجود حل لمسألة SRS لفئة خاصة من الأعداد الصحيحة.