प्राकृतिक संख्याओं के समुच्चय पर परिपथ

प्राकृतिक संख्याओं पर सर्किट (कंप्यूटर सिद्धांत) एक गणितीय नमूना है जिसका उपयोग कम्प्यूटेशनल जटिलता सिद्धांत का अध्ययन करने में किया जाता है। वे सर्किट (कंप्यूटर सिद्धांत) का एक विशेष स्थिति हैं। ऑब्जेक्ट एक लेबल निर्देशित अचक्रीय ग्राफ के रूप में प्रस्तुत किया जाता है, जिसके नोड नैसर्गिक संख्याओं के सेट का मूल्यांकन करते हैं, पत्तियाँ सीमित संख्या के सेट होती हैं, और द्वार सेट ऑपरेशन या अंकगणितीय ऑपरेशन होते हैं।

कलन विधि समस्या के रूप में, समस्या यह पता लगाने की है कि क्या दी गई प्राकृतिक संख्या आउटपुट नोड का एक तत्व है या यदि दो सर्किट एक ही सेट की गणना करते हैं। निर्णायकता अभी भी एक खुला प्रश्न है।

औपचारिक परिभाषा

प्राकृतिक संख्या सर्किट एक सर्किट जटिलता होता है, अर्थात अधिकतम 2 में इन-डिग्री का निर्देशित एसाइक्लिक ग्राफ, इन-डिग्री 0 के नोड्स, पत्तियां, प्राकृतिक संख्याओं के परिमित सेट हैं, इन-डिग्री के नोड्स के लेबल 1 होते हैं −, जहां ${\overline {A}}=\{x\in \mathbb {N} |x\not \in A\}$ और इन-डिग्री 2 के नोड्स के लेबल +, ×, ∪ और ∩ होते हैं, जहां $A+B=\{a+b|a\in A,b\in B\}$, $A\times B=\{a\times b|a\in A,b\in B\}$ और ∪ और ∩ सामान्य सेट (गणित) अर्थ के साथ होता है।

सर्किट के उपसमूह का भी अध्ययन किया जाता है जो सभी संभावित लेबल का उपयोग नहीं करते हैं।

एल्गोरिदमिक समस्याएं

यह प्रश्न पूछ सकते है:

• क्या एक दिए गए संख्या n आउटपुट नोड का सदस्य है?
• क्या आउटपुट नोड खाली है?
• क्या एक नोड दूसरे नोड का एक उपसेट है?

सर्किट के लिए जो सभी लेबल का उपयोग करते हैं, ये सभी समस्याएं समतुल्य होती हैं।

प्रमाण

पहली समस्या को दूसरी समस्या में घटाया जा सकता है, जोकि आउटपुट गेट और n का छेदन लेने द्वारा होता है। वास्तव में, नया आउटपुट गेट खाली होगा यदि और एकमात्र तभी जब n पूर्व आउटपुट गेट का सदस्य नहीं था।

पहली समस्या को तीसरी समस्या में घटाया जा सकता है, जिसमें पूछा जाता है कि क्या नोड n आउटपुट नोड का एक उपसेट है।

दूसरी समस्या को पहली समस्या में घटाया जा सकता है, इसके लिए पर्याप्त है कि आउटपुट गेट को 0 से गुणा करें, फिर 0 आउटपुट गेट में होगा यदि और एकमात्र तभी जब पूर्व आउटपुट गेट खाली नहीं था।

तीसरी समस्या दूसरे के लिए कम करने योग्य है, यह जाँचने के लिए कि क्या A, B का एक उपसमुच्चय है, यह पूछने के बराबर है कि क्या इसमें कोई तत्व $A\cap {\overline {B}}$ है ।

प्रतिबंध

यदि O को {∪,∩,−,+,×} का एक उपसेट माना जाए, तो हम MC(O) को नामकित करते हैं, जो एक प्राकृतिक संख्या को ढूंढने की समस्या है जो सर्किट के गेट के लेबल O में होते हैं, और MF(O) को उसी समस्या का नाम देते हैं कि सर्किट एक पेड़ होनी चाहिए, जिसमें यह अतिरिक्त शर्त लगाई जाती है।

तेजी से बढ़ने वाला सेट

एक कठिनाई इस तथ्य से आती है कि एक परिमित समुच्चय का पूरक अनंत है, और एक कंप्यूटर के पास एकमात्र एक परिमित स्मृति होती है। लेकिन उपसारण के बिना भी, डबल एक्सपोनेंशियल फ़ंक्शन नंबर बना सकते हैं। लेट $E_{0}=\{2\},E_{i+1}=E_{i}\times E_{i}$, तो कोई आसानी से इंडक्शन के माध्यम से सिद्ध कर सकता है $i$ वह $E_{i}=\{2^{2^{i}}\}$, वास्तव में $E_{0}=\{2\}=\{2^{1}\}=\{2^{2^{0}}\}$ और प्रेरण के माध्यम से $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}}\}$.

और यहां तक ​​कि डबल एक्सपोनेंशियल-साइज़ सेट: लेट $S_{0}=\{0,1,2\},S_{i+1}=(S_{i}\times S_{i})+S_{i}$, तब $\{x|0<x<2^{2^{i}}\}\subset S_{i}$, अर्थात। $S_{i}$ सम्मलित है $2^{2^{i}}$ पहला नंबर। एक बार फिर इसे इंडक्शन ऑन करके सिद्ध किया जा सकता है $i$, के लिए सत्य है $S_{0}$ परिभाषा के अनुसार और चलो $x\in \{x|0<x<2^{2^{i+1}}\}$, विभाजित करना $x$ के माध्यम से $2^{2^{i}}$ हम देखते हैं कि इसे लिखा जा सकता है $x=2^{2^{i}}\times d+r$ कहाँ $d,r<2^{2^{i}}$, और प्रेरण द्वारा, $2^{2^{i}},d$ और $r$ में हैं $S_{i}$, वास्तव में $x\in (S_{i}\times S_{i})+S_{i}$.

ये उदाहरण बताते हैं कि जोड़ और गुणा उच्च जटिलता की समस्याएँ उत्पन्न करने के लिए पर्याप्त क्यों हैं।

जटिलता परिणाम

सदस्यता समस्या

सदस्यता समस्या पूछती है कि क्या एक तत्व n और एक सर्किट दिया गया है, n सर्किट के आउटपुट गेट में है।

जब अधिकृत गेट की श्रेणी सीमित होती है, तो सदस्यता समस्या प्रसिद्ध कम्प्लेक्सिटी कक्षाओं के अंदर होती है। ध्यान दें कि यहां आकार चर माना जाता है; सर्किट या पेड़ का आकार; n का मान माना जाता है कि यह निश्चित है।

जटिलता

O	MC(O)	MF(O)
∪,∩,−,+,×	नेक्स्टटाइम-कठिन हॉल्टिंग समस्या के लिए ऑरेकल के साथ निर्णय लेने योग्य	PSPACE-hard
∪,∩,+,×	NEXPTIME- पूर्ण	NP- पूर्ण
∪,+,×	PSPACE- पूर्ण	NP- पूर्ण
∩,+,×	P-hard, in co-RP	in DLOGCFL
+,×	P- पूर्ण	in DLOGCFL
∪,∩,−,+	PSPACE- पूर्ण	PSPACE- पूर्ण
∪,∩,+	PSPACE- पूर्ण	NP- पूर्ण
∪,+	NP- पूर्ण	NP- पूर्ण
∩,+	C=L- पूर्ण	in L
+	C=L- पूर्ण	in L
∪,∩,−,×	PSPACE- पूर्ण	PSPACE- पूर्ण
∪,∩,×	PSPACE- पूर्ण	NP- पूर्ण
∪,×	NP- पूर्ण	NP- पूर्ण
∩,×	C=L-hard, in P	in L
×	NL- पूर्ण	in L
∪,∩,−	P- पूर्ण	NC1- पूर्ण
∪,∩	P- पूर्ण	in NC1
∪	NL- पूर्ण	in NC1
∩	NL- पूर्ण	in NC1

समानता की समस्या

समानता समस्या पूछती है कि, दिए गए सर्किट के दो गेट के लिए, वे एक ही सेट का मूल्यांकन करते हैं या नहीं करते हैं।

जब अधिकृत गेट की श्रेणी सीमित होती है, तो समानता समस्या प्रसिद्ध कम्प्लेक्सिटी कक्षाओं के अंदर होती है। हम EC(O) और EF(O) को समानता समस्या का नाम देते हैं, जहां सर्किट और सूत्र के गेट O में होते हैं।

जटिलता

O	EC(O)	EF(O)
∪,∩,−,+,×	नेक्स्टटाइम-कठिन हॉल्टिंग समस्या के लिए ऑरेकल के साथ निर्णय लेने योग्य	नेक्स्टटाइम-कठिन हॉल्टिंग समस्या के लिए ऑरेकल के साथ निर्णय लेने योग्य
∪,∩,+,×	NEXPTIME-hard, in coNEXPNP	ΠP2- पूर्ण
∪,+,×	NEXPTIME-hard, in coNEXPNP	ΠP2- पूर्ण
∩,+,×	P-hard, in BPP	P-hard, in BPP
+,×	P-hard, in BPP	P-hard, in coRP
∪,∩,−,+	PSPACE- पूर्ण	PSPACE- पूर्ण
∪,∩,+	PSPACE- पूर्ण	ΠP2- पूर्ण
∪,+	ΠP2- पूर्ण	ΠP2- पूर्ण
∩,+	coC=L(2)- पूर्ण	in L
+	C=L- पूर्ण	in L
∪,∩,−,×	PSPACE- पूर्ण	PSPACE- पूर्ण
∪,∩,×	PSPACE- पूर्ण	ΠP2- पूर्ण
∪,×	ΠP2- पूर्ण	ΠP2- पूर्ण
∩,×	coC=L(2)-hard, in P	in L
×	C=L-hard, in P	in L
∪,∩,−	P- पूर्ण	NC1- पूर्ण
∪,∩	P- पूर्ण	NC1- पूर्ण
∪	NL- पूर्ण	in NC1
∩	NL- पूर्ण	in NC1

संदर्भ

• Travers, Stephen (2006), "The Complexity of Membership Problems for Circuits over Sets of Natural Numbers", Theoretical Computer Science, 389 (1): 211–229, doi:10.1016/j.tcs.2006.08.017, ISSN 0304-3975

• Pierre McKenzie; Klaus W. Wagner (2003), "The Complexity of Membership Problems for Circuits over Sets of Natural Numbers", Lecture Notes in Computer Science, Springer-Verlag, 2607: 571–582, doi:10.1007/3-540-36494-3_50, ISBN 3-540-00623-0

• Breunig, Hans-Georg (2007), The complexity of membership problems for circuits over sets of positive numbers, vol. FCT'07 Proceedings of the 16th international conference on Fundamentals of Computation Theory, Springer-Verlag, pp. 125–136, ISBN 978-3-540-74239-5

बाहरी संबंध

• Pierre McKenzie, The complexity of circuit evaluation over the natural numbers