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

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

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

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

एक प्राकृतिक संख्या सर्किट एक सर्किट जटिलता है, यानी अधिकतम 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 आउटपुट नोड का सदस्य है।
• क्या आउटपुट नोड खाली है?
• क्या एक नोड दूसरे का उपसमुच्चय है।

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

प्रमाण

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

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

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

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

प्रतिबंध

O को {∪,∩,−,+,×} का एक उपसमुच्चय होने दें, फिर हम MC(O) को यह पता लगाने की समस्या कहते हैं कि क्या एक प्राकृतिक संख्या एक सर्किट के आउटपुट गेट के अंदर है, जिसके गेट्स के लेबल 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 का मान स्थिर माना जाता है।

Complexity

O	MC(O)	MF(O)
∪,∩,−,+,×	NEXPTIME-hard Decidable with an oracle for the halting problem	PSPACE-hard
∪,∩,+,×	NEXPTIME-complete	NP-complete
∪,+,×	PSPACE-complete	NP-complete
∩,+,×	P-hard, in co-RP	in DLOGCFL
+,×	P-complete	in DLOGCFL
∪,∩,−,+	PSPACE-complete	PSPACE-complete
∪,∩,+	PSPACE-complete	NP-complete
∪,+	NP-complete	NP-complete
∩,+	C=L-complete	in L
+	C=L-complete	in L
∪,∩,−,×	PSPACE-complete	PSPACE-complete
∪,∩,×	PSPACE-complete	NP-complete
∪,×	NP-complete	NP-complete
∩,×	C=L-hard, in P	in L
×	NL-complete	in L
∪,∩,−	P-complete	NC1-complete
∪,∩	P-complete	in NC1
∪	NL-complete	in NC1
∩	NL-complete	in NC1

तुल्यता समस्या

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

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

Complexity

O	EC(O)	EF(O)
∪,∩,−,+,×	NEXPTIME-hard Decidable with an oracle for the halting problem	PSPACE-hard Decidable with an oracle for the halting problem
∪,∩,+,×	NEXPTIME-hard, in coNEXPNP	ΠP2-complete
∪,+,×	NEXPTIME-hard, in coNEXPNP	ΠP2-complete
∩,+,×	P-hard, in BPP	P-hard, in BPP
+,×	P-hard, in BPP	P-hard, in coRP
∪,∩,−,+	PSPACE-complete	PSPACE-complete
∪,∩,+	PSPACE-complete	ΠP2-complete
∪,+	ΠP2-complete	ΠP2-complete
∩,+	coC=L(2)-complete	in L
+	C=L-complete	in L
∪,∩,−,×	PSPACE-complete	PSPACE-complete
∪,∩,×	PSPACE-complete	ΠP2-complete
∪,×	ΠP2-complete	ΠP2-complete
∩,×	coC=L(2)-hard, in P	in L
×	C=L-hard, in P	in L
∪,∩,−	P-complete	NC1-complete
∪,∩	P-complete	NC1-complete
∪	NL-complete	in NC1
∩	NL-complete	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