تعقيد الدوائر الحسابية

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 52 صور
الموسوعة الحرة

في نظرية التعقيد الحسابي ، تُعدّ الدوائر الحسابية النموذج القياسي لحساب كثيرات الحدود . ببساطة، تأخذ الدائرة الحسابية كمدخلات إما متغيرات أو أرقامًا، ويُسمح لها إما بجمع أو ضرب تعبيرين سبق حسابهما. توفر الدوائر الحسابية طريقة رسمية لفهم تعقيد حساب كثيرات الحدود. يتمثل السؤال الأساسي في هذا المجال البحثي في: "ما هي الطريقة الأكثر كفاءة لحساب كثيرة حدود معينة؟"و{\displaystyle f}"

التعريفات

دائرة حسابية بسيطة(x1+x2)x2(x2+1){\displaystyle (x_{1}+x_{2})x_{2}(x_{2}+1)}.

دائرة حسابيةج{\displaystyle C}في الملعبF{\displaystyle F}ومجموعة المتغيراتx1،...،xن{\displaystyle x_{1},\ldots ,x_{n}}هو رسم بياني موجه غير دوري كما يلي. كل عقدة فيه ذات درجة داخلية صفرية تسمى بوابة إدخال ويتم تسميتها إما بمتغيرxأنا{\displaystyle x_{i}}أو عنصر حقل فيF.{\displaystyle F.}كل بوابة أخرى تحمل علامة إما+{\displaystyle +}أو×؛{\displaystyle \times في الحالة الأولى ، تكون بوابة جمع ، وفي الثانية بوابة ضرب . الصيغة الحسابية هي دائرة يكون لكل بوابة فيها درجة خروج تساوي واحدًا (وبالتالي فإن الرسم البياني الأساسي هو شجرة موجهة ).

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

تقوم دائرة حسابية بحساب متعددة الحدود بالطريقة الطبيعية التالية: تقوم بوابة الإدخال بحساب متعددة الحدود التي تحمل اسمها. بوابة الجمعv{\displaystyle v}يحسب مجموع كثيرات الحدود التي تحسبها عناصره الفرعية (بوابة).u{\displaystyle u}هو ابن​v{\displaystyle v}إذا كانت الحافة الموجهة(v،u){\displaystyle (v,u)}(موجودة في الرسم البياني). تحسب بوابة الضرب حاصل ضرب كثيرات الحدود التي تحسبها بواباتها الفرعية. انظر إلى الدائرة في الشكل، على سبيل المثال: تحسب بوابات الإدخال (من اليسار إلى اليمين)x1،x2{\displaystyle x_{1},x_{2}}و1،{\displaystyle 1,}تقوم بوابات الجمع بحسابx1+x2{\displaystyle x_{1}+x_{2}}وx2+1،{\displaystyle x_{2}+1,}وتقوم بوابة الضرب بحساب(x1+x2)x2(x2+1).{\displaystyle (x_{1}+x_{2})x_{2}(x_{2}+1).}

ملخص

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

لاحظ أننا مهتمون بالحساب الرسمي لكثيرات الحدود، وليس بالدوال التي تُعرّفها هذه كثيرات الحدود. على سبيل المثال، لنأخذ كثيرة الحدود التالية:x2+x؛{\displaystyle x^{2}+x;}على حقل عنصرين، تمثل هذه متعددة الحدود الدالة الصفرية، لكنها ليست متعددة الحدود الصفرية نفسها. هذا أحد الفروق بين دراسة الدوائر الحسابية ودراسة الدوائر المنطقية . في التعقيد المنطقي، ينصب الاهتمام في الغالب على حساب دالة، وليس على تمثيلها (في حالتنا، تمثيلها بمتعددة حدود). وهذا أحد الأسباب التي تجعل التعقيد المنطقي أصعب من التعقيد الحسابي. ويمكن اعتبار دراسة الدوائر الحسابية إحدى الخطوات الوسيطة نحو دراسة الحالة المنطقية، [ 1 ] التي يصعب علينا فهمها.

الحدود العليا

في إطار دراسة تعقيد حساب كثيرات الحدود، تم اكتشاف بعض الدوائر الذكية (أو الخوارزميات). ومن الأمثلة المعروفة خوارزمية ستراسن لحساب حاصل ضرب المصفوفات . وهي الطريقة المباشرة لحساب حاصل ضرب مصفوفتين.ن×ن{\displaystyle n\times n}تتطلب المصفوفات دائرة بحجم من رتبةن3.{\displaystyle n^{3}.}أظهر ستراسن أنه يمكننا بالفعل ضرب مصفوفتين باستخدام دائرة بحجم تقريبين2.807.{\displaystyle n^{2.807}.}تتمثل الفكرة الأساسية لستراسن في طريقة ذكية للضرب.2×2{\displaystyle 2\times 2}المصفوفات. هذه الفكرة هي نقطة الانطلاق لأفضل طريقة نظرية لضرب مصفوفتين تستغرق وقتًا تقريبًان2.376.{\displaystyle n^{2.376}.}

ثمة قصة أخرى مثيرة للاهتمام وراء حساب محدد مصفوفةن×ن{\displaystyle n\times n}المصفوفة. تتطلب الطريقة البسيطة لحساب المحدد دوائر بحجم تقريبين!.{\displaystyle n!.}ومع ذلك، نعلم أن هناك دوائر بحجم متعدد الحدود فين{\displaystyle n}لحساب المحدد. ومع ذلك، فإن عمق هذه الدوائر خطي فين.{\displaystyle n.}توصل بيركويتز إلى تحسين: دائرة بحجم متعدد الحدود فين،{\displaystyle n,}لكن بعمقيا(سجل2⁡(ن)).{\displaystyle O(\log ^{2}(n)).}[ 2 ]

نود أيضًا أن نذكر أفضل دائرة معروفة بـ ...ن×ن{\displaystyle n\times n}المصفوفة. أما بالنسبة للمحدد، فإن الدائرة البسيطة للمتغير الدائم لها حجم تقريبين!.{\displaystyle n!.}ومع ذلك، بالنسبة للدائرة الدائمة، فإن أفضل دائرة معروفة يبلغ حجمها تقريبًا2ن،{\displaystyle 2^{n},}والتي تُعطى بواسطة صيغة رايزر: لـن×ن{\displaystyle n\times n}مصفوفةX=(xأنا،ج)،{\displaystyle X=(x_{i,j}),}

موج الشعر بإستمرار⁡(X)=(-1)ن∑S⊆{1،...،ن}(-1)|S|∏أنا=1ن∑ج∈Sxأنا،ج{\displaystyle \operatorname {perm} (X)=(-1)^{n}\sum _{S\subseteq \{1,\ldots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}x_{i,j}}

(هذه دائرة من العمق الثالث).

الحدود الدنيا

فيما يتعلق بإثبات الحدود الدنيا، فإن معرفتنا محدودة للغاية. وبما أننا ندرس حساب كثيرات الحدود الرسمية، فإننا نعلم أن كثيرات الحدود ذات الدرجة العالية جدًا تتطلب دوائر كهربائية كبيرة، على سبيل المثال، كثيرة حدود من الدرجة22ن{\displaystyle 2^{2^{n}}}يتطلب الأمر دائرة بحجم تقريبًا2ن.{\displaystyle 2^{n}.}إذن، الهدف الرئيسي هو إثبات حد أدنى لكثيرات الحدود ذات الدرجة الصغيرة، على سبيل المثال، كثيرة الحدود فين.{\displaystyle n.}في الواقع، كما هو الحال في العديد من فروع الرياضيات ، تُشير حجج العدّ إلى وجود كثيرات حدود من الدرجة تتطلب دوائر بحجم أكبر من كثيرات الحدود. مع ذلك، لا تُحسّن هذه الحجج عادةً فهمنا للحساب. وتُعدّ المسألة التالية هي المشكلة الرئيسية المفتوحة في هذا المجال البحثي: إيجاد كثيرة حدود صريحة من الدرجة تتطلب دوائر بحجم أكبر من كثيرات الحدود .

أحدث التقنيات هيΩ(نسجل⁡د){\displaystyle \Omega (n\log d)}الحد الأدنى لحجم الدائرة الحسابية، على سبيل المثال، متعدد الحدودx1د+⋯+xند{\displaystyle x_{1}^{d}+\cdots +x_{n}^{d}}قدمها ستراسن وباور وستراسن. وبشكل أدق، استخدم ستراسن نظرية بيزو لإثبات أن أي دائرة تحسب في آن واحدن{\displaystyle n}كثيرات الحدودx1د،...،xند{\displaystyle x_{1}^{d},\ldots ,x_{n}^{d}}حجمهΩ(نسجل⁡د)،{\displaystyle \Omega (n\log d),}وفي وقت لاحق، أظهر باور وستراسن ما يلي: بالنظر إلى دائرة حسابية بحجمs{\displaystyle s}حساب متعدد الحدودو،{\displaystyle f,}يمكن للمرء أن يبني دائرة جديدة بحجم أقصىيا(s){\displaystyle O(s)}التي تحسبو{\displaystyle f}وجميعن{\displaystyle n}المشتقات الجزئية لـو.{\displaystyle f.}بما أن المشتقات الجزئية لـx1د+⋯+xند{\displaystyle x_{1}^{d}+\cdots +x_{n}^{d}}نكوندx1د-1،...،دxند-1،{\displaystyle dx_{1}^{d-1},\ldots ,dx_{n}^{d-1},}ينطبق الحد الأدنى لـ Strassen علىx1د+⋯+xند{\displaystyle x_{1}^{d}+\cdots +x_{n}^{d}}كذلك. [ 3 ] هذا مثال واحد حيث يساعد وجود حد أعلى في إثبات الحدود الدنيا؛ إن بناء الدائرة الذي قدمه باور وستراسن يستلزم حدًا أدنى لكثيرات الحدود الأكثر عمومية.

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

P و NP الجبرية

تُعدّ مسألة P مقابل NP من أكثر المسائل المفتوحة إثارةً للاهتمام في نظرية التعقيد الحسابي . وتتلخص هذه المسألة، باختصار، في تحديد ما إذا كان بالإمكان حلّ مسألة معينة بسهولةٍ تُضاهي سهولة إثبات وجود حلّ لها. وقد اقترح فاليانت، في عمله الرائد [ 4 ] ، نظيرًا جبريًا لهذه المسألة، وهو مسألة VP مقابل VNP .

تُعتبر الفئة VP النظير الجبري للفئة P؛ وهي فئة كثيرات الحدود و{\displaystyle f}من الدرجة متعددة الحدود التي لها دوائر بحجم متعدد الحدود على حقل ثابتك.{\displaystyle K.}تُعتبر فئة VNP نظيرًا لفئة NP. ويمكن اعتبار VNP فئة من كثيرات الحدودو{\displaystyle f}من درجة متعددة الحدود بحيث يمكننا تحديد معاملها عند إعطاء حد وحيدو{\displaystyle f}بكفاءة، مع دائرة ذات حجم متعدد الحدود.

يُعد مفهوم الاكتمال أحد المفاهيم الأساسية في نظرية التعقيد . فعند النظر إلى فئة من كثيرات الحدود (مثل VP أو VNP)، فإن كثيرة الحدود الكاملة هيو{\displaystyle f}بالنسبة لهذه الفئة، فإن متعددة الحدود لها خاصيتان: (1) أنها جزء من الفئة، و(2) أي متعددة حدود أخرىز{\displaystyle g}في الفصل أسهل منو،{\displaystyle f,}بمعنى أنه إذاو{\displaystyle f}إذا كانت الدائرة صغيرة، فكذلكز.{\displaystyle g.}أثبت فاليانت أن الدائرة الدائمة كاملة بالنسبة للفئة VNP. لذا، لإثبات أن VP لا تساوي VNP، يجب إثبات أن الدائرة الدائمة لا تحتوي على دوائر ذات حجم متعدد الحدود. ولا تزال هذه المسألة مفتوحة البحث.

تقليل العمق

يُعدّ عمل فاليانت، وسكايم، وبيركويتز، وراكوف أحد أهمّ المراجع في فهمنا لحساب كثيرات الحدود. [ 5 ] لقد أظهروا أنه إذا كانت كثيرة الحدودو{\displaystyle f}درجة علميةر{\displaystyle r}يحتوي على دائرة بحجمs،{\displaystyle s,}ثمو{\displaystyle f}كما يحتوي على دائرة بحجم متعدد الحدود فير{\displaystyle r}وs{\displaystyle s}عمقيا(سجل⁡(ر)سجل⁡(s)).{\displaystyle O(\log(r)\log(s)).}على سبيل المثال، أي كثير حدود من الدرجةن{\displaystyle n}يحتوي على دائرة ذات حجم متعدد الحدود، كما يحتوي على دائرة ذات حجم متعدد الحدود بعمق تقريبيسجل2⁡(ن).{\displaystyle \log ^{2}(n).}تعمم هذه النتيجة دائرة بيركويتز لتشمل أي متعددة حدود من الدرجة α ذات دائرة بحجم متعدد الحدود (مثل المحدد). ويُعتقد أن نظير هذه النتيجة في السياق البولياني خاطئ.

إحدى نتائج هذه النتيجة هي محاكاة الدوائر باستخدام صيغ صغيرة نسبيًا، صيغ ذات حجم شبه متعدد الحدود: إذا كان متعدد الحدودو{\displaystyle f}درجة علميةر{\displaystyle r}يحتوي على دائرة بحجمs،{\displaystyle s,}ثم يكون لها صيغة للحجمsيا(سجل⁡(ر)).{\displaystyle s^{O(\log(r))}.}تُعد هذه المحاكاة أسهل من تقليل العمق الذي قام به فاليانت وآخرون، وقد أظهرها هيافيل سابقًا. [ 6 ]

انظر أيضاً

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

الحواشي

  1. ↑ إل جي فاليانت. لماذا تعتبر نظرية التعقيد البولياني صعبة؟ وقائع ندوة جمعية لندن الرياضية حول تعقيد الدوال البوليانية، الصفحات 84-94، 1992.
  2. ↑ إس جيه بيركويتز. حول حساب المحدد في وقت متوازي قصير باستخدام عدد قليل من المعالجات. رسائل إنتاج المعلومات 18، ص 147-150، 1984.
  3. ↑ شبيلكا، أمير؛ يهودايوف، أمير (2010). "دوائر الحساب: مسح للنتائج الحديثة والأسئلة المفتوحة" (ملف PDF) . أسس واتجاهات في علوم الحاسوب النظرية . 5 ( 3-4 ): 207-388. doi : 10.1561/0400000039 .
  4. ↑ فاليانت، إل جي (1979). "فئات الاكتمال في الجبر". وقائع الندوة السنوية الحادية عشرة لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '79 . مطبعة جمعية آلات الحوسبة. الصفحات 249-261 . doi : 10.1145/800135.804419 . 
  5. ↑ فاليانت، إل جي؛ سكيوم، إس؛ بيركويتز، إس؛ راكوف، سي. (1983). "الحساب المتوازي السريع لكثيرات الحدود باستخدام عدد قليل من المعالجات" . مجلة SIAM للحوسبة . 12 (4): 641-644 . doi : 10.1137/0212043 . ISSN 0097-5397 . 
  6. ↑ هيافيل، لوران (1979). "حول التقييم المتوازي لكثيرات الحدود متعددة المتغيرات" . مجلة SIAM للحوسبة . 8 (2): 120-123 . doi : 10.1137/0208010 . ISSN 0097-5397 .