دائرة الأعداد الصحيحة

في نظرية التعقيد الحسابي ، تعتبر الدائرة الصحيحة نموذجًا للدائرة الحسابية حيث تكون مدخلات الدائرة عبارة عن مجموعات من الأعداد الصحيحة وتقوم كل بوابة من بوابات الدائرة بحساب إما عملية مجموعة أو عملية حسابية على مجموعات الإدخال الخاصة بها.

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

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

تُعرف مسألة الانتماء بأنها مسألة تحديد ما إذا كان العدد الصحيح n موجودًا في مخرج الدائرة C عند إدخال المدخل X، وذلك عند وجود دائرة عددية صحيحة C، ومدخل للدائرة X ، وعدد صحيح محدد n . يعتمد التعقيد الحسابي لهذه المسألة على نوع البوابات المسموح بها في الدائرة C. ^{[ 1 ]} يلخص الجدول أدناه التعقيد الحسابي لمسألة الانتماء لفئات مختلفة من الدوائر العددية الصحيحة. هنا، MF${\displaystyle _{\mathbb {Z} }}$يشير (O) إلى الفئات المحددة بواسطة صيغ O، وهي دوائر O ذات أقصى عدد من المراوح 1.

تعقيد

يا	مقدم الحفل${\displaystyle _{\mathbb {Z} }}$(O)	MF${\displaystyle _{\mathbb {Z} }}$(O)
∪,∩, − ,+,×	التجربة التالية - صعب	بي سبيس - صعب
∪,∩,+,×	الوقت التالي - مكتمل	NP-complete
∪,+,×	الوقت التالي - مكتمل	NP-complete
∩,+,×	P -hard، في co-NP	L -hard, in LOGCFL
+,×	P -hard، في co-NP	L -hard, in LOGCFL
∪,∩, − ,+	PSPACE - مكتمل	PSPACE - مكتمل
∪,∩,+	PSPACE - مكتمل	NP-complete
∪,+	NP-complete	NP-complete
∩,+	C = L - مكتمل	L - مكتمل
+	C = L - مكتمل	L - مكتمل
∪,∩, − ,×	PSPACE - مكتمل	PSPACE - مكتمل
∪,∩,×	PSPACE - مكتمل	NP-complete
∪,×	NP-complete	NP-complete
∩,×	( ج = ل)${\displaystyle \land \oplus }$L)-صلب، في P	L - مكتمل
×	( NL -كامل)${\displaystyle \land \oplus }$L)-كامل	L - مكتمل
∪,∩, −	P - مكتمل	L - مكتمل
∪,∩	P - مكتمل	L - مكتمل
∪	NL - كامل	L - مكتمل
∩	NL - كامل	L - مكتمل