دائرة منطقية

لا تعمل دائرة معينة إلا على مدخلات ذات حجم ثابت. مع ذلك، تحتوي اللغات الرسمية ( التمثيلات النصية لمسائل القرار ) على سلاسل نصية بأطوال مختلفة، لذا لا يمكن تمثيل اللغات بالكامل بواسطة دائرة واحدة (على عكس نموذج آلة تورينج، حيث تُوصف اللغة بالكامل بواسطة آلة تورينج واحدة). بدلاً من ذلك، تُمثل اللغة بواسطة عائلة من الدوائر . عائلة الدوائر هي قائمة لا نهائية من الدوائر.${\displaystyle (C_{0},C_{1},C_{2},...)}$، أين${\displaystyle C_{n}}$لديه${\displaystyle n}$متغيرات الإدخال. يقال إن عائلة الدوائر تحدد لغة ما.${\displaystyle L}$إذا، لكل سلسلة${\displaystyle w}$،${\displaystyle w}$مكتوبة باللغة${\displaystyle L}$إذا وفقط إذا${\displaystyle C_{n}(w)=1}$، أين${\displaystyle n}$هو طول${\displaystyle w}$بمعنى آخر، اللغة هي مجموعة السلاسل التي، عند تطبيقها على الدوائر المقابلة لأطوالها، تُقيّم إلى 1. ^{[ 2 ] : 354}

يمكن تحديد عدة مقاييس مهمة للتعقيد في الدوائر المنطقية، بما في ذلك عمق الدائرة، وحجمها، وعدد التبديلات بين بوابات "و" وبوابات "أو". على سبيل المثال، يُعرَّف تعقيد حجم الدائرة المنطقية بأنه عدد البوابات الموجودة فيها.

ثمة علاقة طبيعية بين تعقيد حجم الدائرة وتعقيد الوقت . ^{[ 2 ] : 355.} وبشكل بديهي، فإن اللغة ذات التعقيد الزمني المنخفض (أي التي تتطلب عددًا قليلًا نسبيًا من العمليات المتسلسلة على آلة تورينج ) تتميز أيضًا بتعقيد دائرة منخفض (أي التي تتطلب عددًا قليلًا نسبيًا من العمليات المنطقية). ويمكن إثبات أنه إذا كانت اللغة في${\displaystyle {\mathsf {TIME}}(t(n))}$، أين${\displaystyle t}$هي دالة${\displaystyle t:\mathbb {N} \to \mathbb {N} }$ثم يصبح حجم الدائرة معقدًا${\displaystyle O(t^{2}(n))}$.

تُعرَّف عدة فئات تعقيد مهمة بدلالة الدوائر المنطقية. وأكثرها عموميةً هي P/poly ، وهي مجموعة اللغات التي يمكن تقريرها بواسطة عائلات دوائر ذات حجم متعدد الحدود. وينتج ذلك مباشرةً من حقيقة أن اللغات في${\displaystyle {\mathsf {TIME}}(t(n))}$تتميز بتعقيد الدوائر${\displaystyle O(t^{2}(n))}$ذلك P${\displaystyle \subseteq }$P/poly. بعبارة أخرى، أي مسألة يمكن حلها في وقت متعدد الحدود بواسطة آلة تورينج حتمية، يمكن حلها أيضًا بواسطة عائلة دوائر ذات حجم متعدد الحدود. ويتحقق ذلك أيضًا إذا كان التضمين صحيحًا (أي P).${\displaystyle \subsetneq }$(P/poly) لوجود مسائل غير قابلة للحسم ضمن فئة P/poly. تتميز هذه الفئة بعدد من الخصائص التي تجعلها مفيدة للغاية في دراسة العلاقات بين فئات التعقيد. وعلى وجه الخصوص، فهي مفيدة في دراسة المسائل المتعلقة بـ P مقابل NP . فعلى سبيل المثال، إذا وُجدت أي لغة في فئة NP وليست ضمن P/poly، فإن P/poly تصبح P.${\displaystyle \neq }$NP. ^{[ 3 ] : 286} P/poly يساعد أيضًا في دراسة خصائص التسلسل الهرمي متعدد الحدود . على سبيل المثال، إذا كان NP ⊆ P/poly، فإن PH ينهار إلى${\displaystyle \Sigma _{2}^{\mathsf {P}}}$يتوفر وصف كامل للعلاقات بين P/poly وفئات التعقيد الأخرى في قسم " أهمية P/poly ". كما تتميز P/poly بخاصية مثيرة للاهتمام، وهي إمكانية تعريفها بشكل مكافئ على أنها فئة اللغات التي تتعرف عليها آلة تورينغ ذات زمن متعدد الحدود، والتي تمتلك دالة توجيه محدودة متعددة الحدود .

هناك فئتان فرعيتان من P/poly تتميزان بخصائص مثيرة للاهتمام، وهما NC و AC . تُعرَّف هاتان الفئتان ليس فقط من حيث حجم الدائرة، بل أيضًا من حيث عمقها . عمق الدائرة هو طول أطول مسار موجه من عقدة الإدخال إلى عقدة الإخراج. تمثل الفئة NC مجموعة اللغات التي يمكن حلها بواسطة عائلات دوائر لا تقتصر على الحجم متعدد الحدود فحسب، بل تشمل أيضًا العمق متعدد اللوغاريتمات . تُعرَّف الفئة AC بشكل مشابه للفئة NC، إلا أنه يُسمح للبوابات المنطقية بعدد غير محدود من المدخلات (أي يمكن تطبيق بوابتي AND وOR على أكثر من بتين). تُعد الفئة NC فئة مهمة لأنها تمثل فئة اللغات التي تمتلك خوارزميات متوازية فعالة .

تُعدّ مسألة قيمة الدائرة - وهي مسألة حساب مخرجات دائرة منطقية معينة على سلسلة إدخال معينة - مسألة قرار كاملة من فئة P. ^{[ 3 ] : 119} ولذلك، تُعتبر هذه المسألة "متسلسلة بطبيعتها" بمعنى أنه من غير المرجح وجود خوارزمية فعالة ومتوازية للغاية لحلها.

الدوائر المنطقية هي تمثيل مادي لعمليات منطقية بسيطة، مثل AND وOR وNOT (وتراكيبها، كالقلابات غير المتسلسلة أو شبكات الدوائر)، والتي تُشكل بنية رياضية تُعرف بالجبر البولياني . وهي كاملة بمعنى أنها قادرة على تنفيذ أي خوارزمية حتمية. مع ذلك، هذا ليس كل شيء. ففي العالم المادي، نصادف أيضًا العشوائية، لا سيما في الأنظمة الصغيرة التي تخضع لتأثيرات التكميم، والتي تُفسرها نظرية ميكانيكا الكم . لا تستطيع الدوائر المنطقية إنتاج أي عشوائية، ومن هذا المنطلق تُشكل مجموعة منطقية غير مكتملة. يكمن الحل في إضافة مولد بتات عشوائي مخصص إلى الشبكات المنطقية أو الحواسيب، كما هو الحال في آلة تورينج الاحتمالية . وقد قدم بحث حديث ^{[ 4 ]} مفهومًا نظريًا لدائرة منطقية عشوائية بطبيعتها تُسمى القلاب العشوائي ، والذي يُكمل المجموعة. فهو يُوفر العشوائية بشكل ملائم، ويتوافق مع الدوائر المنطقية البوليانية الحتمية. ومع ذلك، فإن البنية الجبرية المكافئة للجبر البولياني والأساليب المرتبطة به لبناء الدوائر واختزالها للمجموعة الموسعة لا تزال غير معروفة.