تعقيد الدوائر

في علم الحاسوب النظري ، يُعدّ تعقيد الدوائر فرعًا من نظرية التعقيد الحسابي، حيث تُصنّف الدوال المنطقية وفقًا لحجم أو عمق الدوائر المنطقية التي تُجريها. ومن المفاهيم ذات الصلة تعقيد الدوائر للغة استرجاعية ، والذي يُحدّد بواسطة مجموعة موحدة من الدوائر.${\displaystyle C_{1},C_{2},\ldots }$(انظر أدناه).

يُعدّ إثبات الحدود الدنيا لحجم الدوائر المنطقية التي تحسب الدوال المنطقية الصريحة منهجًا شائعًا لفصل فئات التعقيد. على سبيل المثال، تتكون فئة الدوائر البارزة P/poly من دوال منطقية قابلة للحساب بواسطة دوائر ذات حجم متعدد الحدود. إثبات أن${\displaystyle {\mathsf {NP}}\not \subseteq {\mathsf {P/poly}}}$سيؤدي ذلك إلى الفصل بين P و NP (انظر أدناه).

تشمل فئات التعقيد المحددة من حيث الدوائر المنطقية AC ⁰ و AC و TC ⁰ و NC ¹ و NC و P/poly .

دائرة منطقية مع${\displaystyle n}$تُعدّ "input bits" رسمًا بيانيًا موجهًا غير دوري، حيث تكون كل عقدة (تُسمى عادةً " بوابات " في هذا السياق) إما عقدة إدخال ذات درجة دخول 0 مُصنّفة بواحدة من${\displaystyle n}$تتكون الدائرة من بتات إدخال، وبوابة AND ، وبوابة OR ، وبوابة NOT . تُحدد إحدى هذه البوابات كبوابة إخراج. تقوم هذه الدائرة بشكل طبيعي بحساب دالة لـ${\displaystyle n}$المدخلات. حجم الدائرة هو عدد البوابات التي تحتويها وعمقها هو أقصى طول للمسار من بوابة الإدخال إلى بوابة الإخراج.

يوجد مفهومان رئيسيان لتعقيد الدوائر. ^{[ 1 ]} تعقيد حجم الدائرة لدالة منطقية${\displaystyle f}$هو الحد الأدنى لحجم أي دائرة حاسوبية${\displaystyle f}$تعقيد عمق الدائرة لدالة منطقية${\displaystyle f}$يمثل الحد الأدنى لعمق أي دائرة حاسوبية${\displaystyle f}$.

تعمّم هذه المفاهيم عند النظر في تعقيد الدوائر لأي لغة رسمية تحتوي على سلاسل ذات أطوال بتات مختلفة، وخاصة اللغات اللانهائية. مع ذلك، لا تسمح الدوائر المنطقية إلا بعدد ثابت من بتات الإدخال. وبالتالي، لا يمكن لأي دائرة منطقية منفردة أن تحدد لغة كهذه. ولمراعاة هذه الإمكانية، يُنظر في مجموعات من الدوائر.${\displaystyle C_{1},C_{2},\ldots }$حيث كل${\displaystyle C_{n}}$يقبل مدخلات بحجم${\displaystyle n}$ستقوم كل عائلة من الدوائر بتوليد اللغة بشكل طبيعي بواسطة الدائرة${\displaystyle C_{n}}$إخراج${\displaystyle 1}$عندما يكون الطول${\displaystyle n}$الخيط هو أحد أفراد العائلة، و${\displaystyle 0}$وإلا، نقول إن مجموعة من الدوائر ذات حجم أدنى إذا لم تكن هناك مجموعة أخرى تحدد المدخلات مهما كان حجمها.${\displaystyle n}$، بدائرة أصغر حجماً من${\displaystyle C_{n}}$(بالنسبة للعائلات ذات العمق الأدنى ). وبالتالي، فإن تعقيد الدوائر له دلالة حتى بالنسبة للغات غير التكرارية . يُمكّن مفهوم العائلة الموحدة من ربط متغيرات تعقيد الدوائر بمقاييس التعقيد القائمة على الخوارزميات للغات التكرارية. مع ذلك، يُفيد المتغير غير الموحد في إيجاد حدود دنيا لمدى تعقيد أي عائلة دوائر لتحديد لغات معينة.

وبالتالي، فإن تعقيد حجم الدائرة للغة رسمية${\displaystyle A}$تُعرَّف بأنها الدالة${\displaystyle t:\mathbb {N} \to \mathbb {N} }$، وهو ما يتعلق بطول البتات في المدخلات،${\displaystyle n}$، إلى تعقيد حجم الدائرة لدائرة مصغرة${\displaystyle C_{n}}$الذي يحدد ما إذا كانت المدخلات ذات الطول المحدد موجودة${\displaystyle A}$يتم تعريف تعقيد عمق الدائرة بشكل مماثل.

تُعدّ الدوائر المنطقية من أبرز الأمثلة على ما يُسمى بنماذج الحوسبة غير المنتظمة ، حيث تُعالج المدخلات ذات الأطوال المختلفة بواسطة دوائر مختلفة، وذلك على عكس النماذج المنتظمة مثل آلات تورينج، حيث يُستخدم نفس الجهاز الحسابي لجميع أطوال المدخلات الممكنة. وبالتالي، ترتبط كل مسألة حسابية بفئة معينة من الدوائر المنطقية.${\displaystyle C_{1},C_{2},\dots }$حيث كل${\displaystyle C_{n}}$هي الدائرة التي تعالج مدخلات من n بت. غالبًا ما يُفرض شرط التوحيد على هذه العائلات، مما يتطلب وجود آلة تورينج، ربما محدودة الموارد ، والتي تُنتج، عند إدخال n ، وصفًا للدائرة الفردية.${\displaystyle C_{n}}$عندما يكون زمن تشغيل آلة تورينج هذه متعدد الحدود بالنسبة إلى n ، يُقال إن عائلة الدوائر متجانسة من النوع P. ويُعدّ شرط تجانس DLOGTIME الأكثر صرامة ذا أهمية خاصة في دراسة فئات الدوائر ذات العمق الضحل مثل AC ⁰ أو TC ^0. عندما لا تُحدد حدود للموارد، تكون اللغة تكرارية (أي قابلة للتقرير بواسطة آلة تورينج) إذا وفقط إذا تم تقريرها بواسطة عائلة متجانسة من الدوائر المنطقية.

يعود مفهوم تعقيد الدوائر إلى شانون عام 1949، ^{[ 2 ]} الذي أثبت أن جميع الدوال المنطقية تقريبًا على n متغيرًا تتطلب دوائر بحجم Θ(2n ^/ n ) . على الرغم من هذه الحقيقة، لم يتمكن علماء نظرية التعقيد حتى الآن من إثبات حد أدنى فوق الخطي لأي دالة صريحة.

تم إثبات الحدود الدنيا فائقة متعددة الحدود في ظل قيود معينة على عائلة الدوائر المستخدمة. أول دالة تم إثبات حدودها الدنيا فائقة متعددة الحدود هي دالة التكافؤ ، التي تحسب مجموع بتات إدخالها بتردد 2. وقد تم إثبات حقيقة أن التكافؤ غير موجود في AC ⁰ بشكل مستقل لأول مرة من قبل أجتاي في عام 1983 ^{[ 3 ] [ 4 ]} ومن قبل فورست وساكس وسيبسر في عام 1984 ^{[ 5 ].} وأثبتت التحسينات اللاحقة التي أجراها هاستاد في عام 1987 ^{[ 6 ]} أن أي عائلة من الدوائر ذات العمق الثابت التي تحسب دالة التكافؤ تتطلب حجمًا أُسّيًا. وبتوسيع نتيجة رازبوروف ^{[ 7 ]} ، أثبت سمولينسكي في عام 1987 ^{[ 8 ]} أن هذا صحيح حتى لو تم تعزيز الدائرة ببوابات تحسب مجموع بتات إدخالها بتردد عدد أولي فردي p .

تتمثل مشكلة الزمرة k في تحديد ما إذا كان الرسم البياني المعطى ذو n رأسًا يحتوي على زمرة بحجم k . لأي اختيار محدد للثوابت n و k ، يمكن ترميز الرسم البياني ثنائيًا باستخدام${\displaystyle {n \choose 2}}$البتات، التي تشير إلى وجود كل حافة ممكنة. ثم يتم صياغة مشكلة k -clique كدالة${\displaystyle f_{k}:\{0,1\}^{n \choose 2}\to \{0,1\}}$بحيث${\displaystyle f_{k}}$تُخرج الدالة القيمة 1 إذا وفقط إذا احتوى الرسم البياني المُشفّر بواسطة السلسلة على مجموعة فرعية بحجم k . هذه المجموعة من الدوال رتيبة ويمكن حسابها بواسطة مجموعة من الدوائر، ولكن ثبت أنه لا يمكن حسابها بواسطة مجموعة من الدوائر الرتيبة ذات الحجم متعدد الحدود (أي الدوائر التي تحتوي على بوابات AND و OR ولكن بدون نفي). تم تحسين النتيجة الأصلية لرازبوروف في عام 1985 ^{[ 7 ]} لاحقًا إلى حد أدنى للحجم الأسي بواسطة ألون وبوبانا في عام 1987 ^{[ 9 ].} في عام 2008، أظهر روسمان ^{[ 10 ]} أن الدوائر ذات العمق الثابت التي تحتوي على بوابات AND و OR و NOT تتطلب حجمًا${\displaystyle \Omega (n^{k/4})}$لحل مشكلة الزمرة k حتى في الحالة المتوسطة . علاوة على ذلك، توجد دائرة بحجم${\displaystyle n^{k/4+O(1)}}$التي تحسب${\displaystyle f_{k}}$.

في عام 1999، أظهر راز وماكنزي لاحقًا أن التسلسل الهرمي الرتيب لـ NC لانهائي. ^{[ 11 ]}

^{تكمن مشكلة القسمة} الصحيحة في التوزيع المنتظم TC ^0. [ ^{12 ]}

تُعدّ الحدود الدنيا للدوائر الكهربائية صعبة عمومًا. وتشمل النتائج المعروفة ما يلي:

• التكافؤ ليس في AC ⁰ غير المنتظم ، كما أثبت ذلك أجتاي في عام 1983 ^{[ 3 ] [ 4 ]} وكذلك فورست وساكس وسيبسر في عام 1984. ^{[ 5 ]}
• تم إثبات أن TC ⁰ الموحد موجود بشكل صارم في PP بواسطة أليندر . ^{[ 13 ]}
• الفئات O ^P ₂ ، ^{[ 14 ]} PP ^{[ nb 1 ]} و MA /1 ^{[ 15 ]} (MA مع بت واحد من النصيحة) ليست في SIZE ( n ^k ) لأي ثابت k.
• على الرغم من وجود شكوك حول احتواء الفئة غير المنتظمة ACC ⁰ على دالة الأغلبية، إلا أن ويليامز لم يثبت ذلك إلا في عام 2010.${\displaystyle {\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}}$[ ^{16 ]​}

يبقى السؤال مطروحاً حول ما إذا كانت NEXPTIME تحتوي على دوائر TC ⁰ غير منتظمة .

ترتبط براهين الحدود الدنيا للدوائر ارتباطًا وثيقًا بإزالة العشوائية . برهان على أن${\displaystyle {\mathsf {P}}={\mathsf {BPP}}}$وهذا يعني ضمناً أن إما${\displaystyle {\mathsf {NEXP}}\not \subseteq {\mathsf {P/poly}}}$أو أن العنصر الدائم للمصفوفة لا يمكن حسابه بواسطة دوائر حسابية غير منتظمة (كثيرات حدود) ذات حجم ودرجة كثير حدود. ^{[ 17 ]}

في عام ١٩٩٧، أظهر رازبوروف وروديتش أن العديد من الحدود الدنيا المعروفة للدوال المنطقية الصريحة تستلزم وجود ما يُسمى بالخصائص الطبيعية المفيدة ضد فئة الدوائر المعنية. ^{[ ١٨ ]} من ناحية أخرى، فإن الخصائص الطبيعية المفيدة ضد P/poly من شأنها أن تُضعف مولدات الأرقام العشوائية الزائفة القوية. يُفسر هذا غالبًا على أنه حاجز "براهين طبيعية" أمام إثبات الحدود الدنيا القوية للدوائر. في عام ٢٠١٦، أثبت كارموسينو وإمباغليازو وكابانيتس وكولوكولوفا أنه يمكن أيضًا استخدام الخصائص الطبيعية لبناء خوارزميات تعلم فعالة. ^{[ ١٩ ]}

تُعرَّف العديد من فئات تعقيد الدوائر الكهربائية من حيث التسلسلات الهرمية للفئات. لكل عدد صحيح غير سالب i ، توجد فئة NC ⁱ ، تتكون من دوائر ذات حجم متعدد الحدود بعمق${\displaystyle O(\log ^{i}(n))}$باستخدام بوابات AND وOR وNOT ذات عدد محدود من المدخلات . يُعد اتحاد NC لجميع هذه الفئات موضوعًا للدراسة. من خلال النظر في البوابات ذات عدد غير محدود من المدخلات، يمكن إنشاء الفئتين AC ⁱ وAC (التي تساوي NC). يمكن إنشاء العديد من فئات تعقيد الدوائر الأخرى التي لها نفس قيود الحجم والعمق عن طريق السماح بمجموعات مختلفة من البوابات.

إذا كانت لغة معينة،${\displaystyle A}$، ينتمي إلى فئة التعقيد الزمني${\displaystyle {\text{TIME}}(t(n))}$لبعض الوظائف${\displaystyle t:\mathbb {N} \to \mathbb {N} }$، ثم${\displaystyle A}$يتميز بتعقيد الدوائر${\displaystyle {\mathcal {O}}(t(n)\log t(n))}$إذا كانت آلة تورينج التي تقبل اللغة غير واعية (بمعنى أنها تقرأ وتكتب نفس خلايا الذاكرة بغض النظر عن المدخلات)، فإن${\displaystyle A}$يتميز بتعقيد الدوائر${\displaystyle {\mathcal {O}}(t(n))}$[ ^{20 ]​}

الدائرة المنطقية الرتيبة هي دائرة تحتوي فقط على بوابات AND و OR، ولا تحتوي على بوابات NOT. تستطيع الدائرة الرتيبة حساب دالة منطقية رتيبة فقط، وهي دالة.${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$حيث لكل${\displaystyle x,y\in \{0,1\}^{n}}$،${\displaystyle x\leq y\implies f(x)\leq f(y)}$، أين${\displaystyle x\leq y}$هذا يعني أن${\displaystyle x_{i}\leq y_{i}}$للجميع${\displaystyle i\in \{1,\ldots ,n\}}$.

• تصغير الدوائر

• فولمر، هيريبيرت [بالألمانية] (1999). مقدمة في تعقيد الدوائر: منهج موحد . نصوص في علوم الحاسوب النظرية. سلسلة EATCS. ​​دار نشر سبرينغر . ISBN 978-3-540-64310-4.
• فيجنر، إنجو (1987) [نوفمبر 1986]. تعقيد الوظائف المنطقية . سلسلة وايلي تيوبنر في علوم الكمبيوتر. فرانكفورت أم ماين/بيليفيلد، ألمانيا: شركة John Wiley & Sons Ltd. ، و BG Teubner Verlag ، شتوتغارت. رقم ISBN 3-519-02107-2. إل سي سي إن 87-10388 . (12+457 صفحة) (ملاحظة: كان هذا الكتاب في ذلك الوقت مرجعًا مؤثرًا في هذا الموضوع، ويُعرف باسم "الكتاب الأزرق". وهو متاح أيضًا للتنزيل (بصيغة PDF) في الندوة الإلكترونية حول التعقيد الحسابي .)
• زويك، أوري . "ملاحظات محاضرة لدورة أوري زويك حول تعقيد الدوائر" .