الدوائر على مجموعات الأعداد الطبيعية

يمكن للمرء أن يسأل:

• هل الرقم المعطى n عضو في عقدة الإخراج؟
• هل عقدة الإخراج فارغة؟
• هل تُعتبر إحدى العقد مجموعة فرعية من عقدة أخرى؟

بالنسبة للدوائر التي تستخدم جميع التسميات، فإن جميع هذه المشاكل متكافئة.

ليكن O مجموعة جزئية من {∪,∩, − ,+,×}، ثم نسمي MC(O) مشكلة إيجاد ما إذا كان عدد طبيعي موجودًا داخل بوابة الإخراج لدائرة تكون تسميات بواباتها في O، و MF(O) نفس المشكلة مع القيد الإضافي وهو أن الدائرة يجب أن تكون شجرة .

تكمن إحدى الصعوبات في أن متممة مجموعة منتهية هي مجموعة غير منتهية، بينما ذاكرة الحاسوب محدودة. ولكن حتى بدون المتممة، يمكن إنشاء أعداد أسية مضاعفة .${\displaystyle E_{0}=\{2\},E_{i+1}=E_{i}\times E_{i}}$ثم يمكن إثبات ذلك بسهولة بالاستقراء على${\displaystyle i}$الذي - التي${\displaystyle E_{i}=\{2^{2^{i}}\}}$، بالفعل${\displaystyle E_{0}=\{2\}=\{2^{1}\}=\{2^{2^{0}}\}}$وبالحث${\displaystyle E_{i+1}=E_{i}\times E_{i}=\{2^{2^{i}}\}\times \{2^{2^{i}}\}=\{(2^{2^{i}})^{2}\}=\{2^{2^{i}\times 2}\}=\{2^{2^{i+1}}\}}$.

وحتى المجموعات ذات الحجم الأسي المزدوج: دع${\displaystyle S_{0}=\{0,1,2\},S_{i+1}=(S_{i}\times S_{i})+S_{i}}$، ثم${\displaystyle \{x|0<x<2^{2^{i}}\}\subset S_{i}}$، أي${\displaystyle S_{i}}$يحتوي على${\displaystyle 2^{2^{i}}}$الرقم الأول. ومرة ​​أخرى، يمكن إثبات ذلك بالاستقراء الرياضي.${\displaystyle i}$وهذا صحيح بالنسبة لـ${\displaystyle S_{0}}$بحسب التعريف، ودع${\displaystyle x\in \{x|0<x<2^{2^{i+1}}\}}$، تقسيم${\displaystyle x}$بواسطة${\displaystyle 2^{2^{i}}}$نرى أنه يمكن كتابتها على النحو التالي${\displaystyle x=2^{2^{i}}\times d+r}$أين${\displaystyle d,r<2^{2^{i}}}$وبالاستقراء،${\displaystyle 2^{2^{i}},d}$و${\displaystyle r}$في${\displaystyle S_{i}}$إذن بالفعل${\displaystyle x\in (S_{i}\times S_{i})+S_{i}}$.

توضح هذه الأمثلة لماذا يكفي الجمع والضرب لخلق مشاكل ذات تعقيد عالٍ.

تطرح مشكلة العضوية سؤالاً حول ما إذا كان العنصر n موجودًا في بوابة الإخراج للدائرة ، مع الأخذ في الاعتبار عنصرًا ما ودائرة .

عندما تكون فئة البوابات المعتمدة محدودة، فإن مشكلة الانتماء تقع ضمن فئات التعقيد المعروفة. تجدر الإشارة إلى أن متغير الحجم هنا هو حجم الدائرة أو الشجرة؛ ويُفترض أن قيمة n ثابتة.

تتساءل مسألة التكافؤ عما إذا كان، بالنظر إلى بوابتين من بوابات الدائرة، فإنهما تُقيّمان إلى نفس المجموعة.

عندما تكون فئة البوابات المعتمدة محدودة، فإن مشكلة التكافؤ تقع ضمن فئات التعقيد المعروفة. ^{[ 1 ]} نسمي مشكلة التكافؤ على الدوائر والصيغ التي تنتمي بواباتها إلى فئة O بالرمزين EC(O) و EF(O).