zero-knowledge proofs के संदर्भ में, एक arithmetic circuit समीकरणों (equations) की एक प्रणाली है जो NP में एक समस्या को मॉडल करती है।

P vs NP पर हमारे लेख का एक मुख्य बिंदु यह है कि P या NP में किसी भी समस्या के समाधान को Boolean circuit के रूप में मॉडल करके सत्यापित (verify) किया जा सकता है।

फिर, हम मूल समस्या के लिए अपने समाधान को Boolean variables के मानों के एक सेट (जिसे witness कहा जाता है) में परिवर्तित करते हैं, जिसके परिणामस्वरूप Boolean circuit true लौटाता है।

यह लेख ऊपर लिंक किए गए लेख पर आधारित है, इसलिए कृपया पहले उसे पढ़ें।

Boolean circuits के विकल्प के रूप में Arithmetic circuits

किसी समस्या के समाधान का प्रतिनिधित्व करने के लिए Boolean circuit का उपयोग करने का एक नुकसान यह है कि addition या multiplication जैसे arithmetic operations का प्रतिनिधित्व करते समय यह बहुत लंबा (verbose) हो सकता है।

उदाहरण के लिए, यदि हम $a + b = c$ को व्यक्त करना चाहते हैं जहाँ $a = 8, b = 4, c = 12$ है, तो हमें $a$, $b$, और $c$ को बाइनरी नंबरों (binary numbers) में बदलना होगा। बाइनरी नंबर का प्रत्येक बिट एक अलग Boolean variable के अनुरूप होगा। इस उदाहरण में, मान लें कि हमें $a$, $b$, और $c$ को एनकोड करने के लिए 4 बिट्स की आवश्यकता है, जहाँ $a₀$ Least Significant Bit (LSB) का प्रतिनिधित्व करता है, और $a₃$ संख्या $a$ के Most Significant Bit (MSB) का प्रतिनिधित्व करता है, जैसा कि नीचे दिखाया गया है:

• a₃, a₂, a₁, a₀
  • $a = 1000$
• b₃, b₂, b₁, b₀
  • $b = 0100$
• c₃, c₂, c₁, c₀
  • $c = 1100$

(आपको अभी यह जानने की आवश्यकता नहीं है कि किसी संख्या को बाइनरी में कैसे बदला जाए, हम लेख में बाद में इस विधि की व्याख्या करेंगे)।

एक बार जब हम $a$, $b$ और $c$ को बाइनरी में लिख लेते हैं, तो हम एक Boolean circuit लिख सकते हैं जिसके इनपुट सभी बाइनरी अंक $(a₀, a₁, …, c₂, c₃)$ होते हैं। हमारा लक्ष्य एक ऐसा Boolean circuit लिखना है, जो circuit true आउटपुट करे यदि और केवल यदि $a + b = c$ हो।

यह उम्मीद से कहीं अधिक जटिल हो जाता है, जैसा कि नीचे दिए गए बड़े circuit द्वारा प्रदर्शित किया गया है, जो बाइनरी में $a + b = c$ को मॉडल करता है। संक्षिप्तता (brevity) के लिए, हम derivation नहीं दिखा रहे हैं। हम केवल सूत्र दिखाते हैं ताकि यह स्पष्ट किया जा सके कि ऐसा circuit कितना लंबा (verbose) हो सकता है:

Copy
((a₄ ∧ b₄ ∧ c₄) ∨ (¬a₄ ∧ ¬b₄ ∧ c₄) ∨ (¬a₄ ∧ b₄ ∧ ¬c₄) ∨ (a₄ ∧ ¬b₄ ∧ ¬c₄)) ∧

((a₃ ∧ b₃ ∧ ((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (¬a₃ ∧ ¬b₃ ∧ ((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (¬a₃ ∧ b₃ ∧ ¬((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (a₃ ∧ ¬b₃ ∧ ¬((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))))) ∧

((a₂ ∧ b₂ ∧ ((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))) ∨
 (¬a₂ ∧ ¬b₂ ∧ ((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))) ∨
 (¬a₂ ∧ b₂ ∧ ¬((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (a₂ ∧ ¬b₂ ∧ ¬((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))))) ∧

((a₁ ∧ b₁ ∧ c₀) ∨ (¬a₁ ∧ ¬b₁ ∧ c₀) ∨ (¬a₁ ∧ b₁ ∧ ¬c₀) ∨ (a₁ ∧ ¬b₁ ∧ ¬c₀)) ∧

((a₀ ∧ b₀ ∧ c₀) ∨ (¬a₀ ∧ ¬b₀ ∧ c₀) ∨ (¬a₀ ∧ b₀ ∧ ¬c₀) ∨ (a₀ ∧ ¬b₀ ∧ ¬c₀)) ∧

¬ ((a₄ ∧ b₄) ∨
     (b₄ ∧ (a₃ ∧ b₃) ∨ (b₃ ∧ (a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))) ∨
     (a₃ ∧ (a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))))

बात यह है कि, यदि हम Boolean इनपुट्स और बुनियादी Boolean operations (AND, OR, NOT) तक सीमित हैं, तो बुनियादी समस्याओं के लिए circuits का निर्माण करना जल्दी ही जटिल और थकाऊ हो सकता है, खासकर जब उनमें arithmetic शामिल हो।

इसके विपरीत, circuit के अंदर सीधे संख्याओं का प्रतिनिधित्व करना आसान होगा। Boolean सूत्र के साथ addition को मॉडल करने के बजाय, हम सीधे उन संख्याओं पर addition और multiplication का उपयोग करते हैं।

यह लेख यह प्रदर्शित करता है कि P या NP में किसी भी समस्या को arithmetic circuit के साथ मॉडल करना भी संभव है।

Arithmetic Circuits

एक arithmetic circuit समीकरणों की एक प्रणाली है जो केवल addition, multiplication और equality का उपयोग करती है। एक Boolean circuit की तरह, यह जांचता है कि प्रस्तावित इनपुट्स का एक सेट वैध (valid) है, लेकिन समाधान की गणना नहीं करता है।

नीचे arithmetic circuit का हमारा पहला उदाहरण दिया गया है:

Copy
6 = x₁ + x₂
9 = x₁x₂

हम कहते हैं कि एक Boolean circuit satisfied (संतुष्ट) है यदि हमारे पास इनपुट वेरिएबल्स के लिए एक ऐसा असाइनमेंट है जिसके परिणामस्वरूप आउटपुट true होता है। इसी तरह, एक arithmetic circuit संतुष्ट होता है यदि वेरिएबल्स के लिए कोई ऐसा असाइनमेंट है जिससे सभी समीकरण सत्य (true) सिद्ध होते हैं।

उदाहरण के लिए, उपरोक्त circuit x₁ = 3, x₂ = 3 द्वारा संतुष्ट होता है क्योंकि circuit के दोनों समीकरण सत्य सिद्ध होते हैं। इसके विपरीत, circuit x₁ = 1, x₂ = 6 द्वारा संतुष्ट नहीं होता है क्योंकि समीकरण 9 = x₁x₂ सत्य नहीं है।

इसलिए, हम एक arithmetic circuit को circuit में समीकरणों के सेट के साथ interchangeably (समानार्थक रूप से) सोच सकते हैं। इनपुट्स का एक सेट “circuit को संतुष्ट करता है” यदि और केवल यदि वे इनपुट सभी समीकरणों को सत्य बनाते हैं।

Notation and Terminology

एक arithmetic circuit में वेरिएबल्स को signals के रूप में संदर्भित किया जाता है क्योंकि Circom, वह प्रोग्रामिंग भाषा जिसका उपयोग हम ZK Proofs लिखने के लिए करेंगे, उन्हें इसी तरह संदर्भित करती है।

समानता (equality) व्यक्त करने के लिए, हम === ऑपरेटर का उपयोग करेंगे। हम इस notation का उपयोग इसलिए करते हैं क्योंकि Circom इसका उपयोग यह बताने के लिए करता है कि दो signals का मान समान है, इसलिए हमें भी इसे देखने की आदत डाल लेनी चाहिए।

हम इस बात पर जोर देते हैं कि === यह दावा (assert) कर रहा है कि बायां पक्ष (left-hand side) और दायां पक्ष (right-hand side) बराबर हैं। उदाहरण के लिए, निम्नलिखित circuit में:

c === a + b

हम a को b में जोड़कर परिणाम को c में असाइन नहीं कर रहे हैं। इसके बजाय, हम यह मान रहे हैं कि मान a, b, और c इनपुट के रूप में प्रदान किए गए हैं, और हम दावा कर रहे हैं कि उनके बीच एक संबंध (relationship) है। इसका प्रभाव a और b के योग को c होने के लिए constraining (बाध्य) करने का है।

c === a + b को पूरी तरह से assertEq(c, a + b) के समतुल्य समझें। इसी तरह, व्यंजक a + b === c * d पूरी तरह से assertEq(a + b, c * d) के समतुल्य है। संक्षेप में, किसी circuit में इन समीकरणों को सत्यापित करने में यह जाँचना शामिल है कि क्या कुछ शर्तें (constraints) संतुष्ट हैं। वह एजेंट जो अपने witness की वैधता साबित कर रहा है, वह signals को कोई भी मान (value) दे सकता है। हालाँकि, उनका प्रमाण (witness) तभी वैध माना जाएगा जब सभी constraints पूरी होंगी।

उदाहरण के लिए, यदि कोई एजेंट यह साबित करना चाहता है:

Copy
a === b + c + 3
a * u === x * y

तो उन्हें circuit के बाहर से (a, b, c, u, x, y) की आपूर्ति करनी होगी और उन्हें circuit में signals को सौंपना (assign) होगा।

याद रखें, उपरोक्त कोड इसके समतुल्य है:

Copy
assertEq(a, b + c + 3)
assertEq(a * u, x * y)

Arithmetic circuit के लिए एक उपयोगी मानसिक मॉडल (mental model) यह है कि सभी signals को बिना आउटपुट के इनपुट के रूप में माना जाता है।

इस बात को स्पष्ट करने के लिए, हम निम्नलिखित वीडियो में एक दृश्य (visualization) प्रदान करते हैं। सभी signals इनपुट हैं, और assign करने के बजाय जांचने के लिए === का उपयोग किया जाता है।

वीडियो में दिखाए गए circuit को इस प्रकार लिखा जा सकता था:

Copy
z + y === x
x + y === u

अर्थ में किसी बदलाव के बिना।

Arithmetic circuit x === x + 1 का अर्थ x को बढ़ाना (increment) नहीं है। यह बिना किसी समाधान वाला एक arithmetic circuit है क्योंकि x, x + 1 के बराबर नहीं हो सकता। इस प्रकार, constraint को संतुष्ट करना असंभव है।

Arithmetic Circuits की व्याख्या (Interpreting)

निम्नलिखित circuit पर विचार करें:

Copy
x₁(x₁ - 1) === 0
x₁x₂ === x₁

पहला constraint x₁(x₁ - 1) === 0, x₁ के संभावित मानों को केवल 0 या 1 तक सीमित करता है। x₁ के लिए कोई अन्य मान इस constraint को संतुष्ट नहीं करेगा।

दूसरे constraint x₁x₂ === x₁ में हमारे पास दो संभावित परिदृश्य (scenarios) हैं:

• यदि x₁ = 1 है, तो x₂ को भी 1 होना चाहिए, अन्यथा दूसरे constraint को संतुष्ट नहीं किया जा सकता। यदि x₁ = 1 और x₂ ≠ 1 है, तो दूसरा समीकरण 1 * x₂ === 1 हो जाता है जिसे केवल x₂ = 1 द्वारा ही संतुष्ट किया जा सकता है, जो एक टकराव (conflict) पैदा करता है।
• यदि x₁ = 0 है, तो x₂ का कोई भी मान हो सकता है क्योंकि 0x₂ === 0 को संतुष्ट करना बहुत आसान (trivial) है।

(x₁, x₂) के लिए निम्नलिखित assignments सभी वैध witnesses हैं:

• $(x₁, x₂) = (1, 1)$
• $(x₁, x₂) = (0, 2)$
• $(x₁, x₂) = (0, 1337)$
• $(x₁, x₂) = (0, 404)$

याद रखें, समीकरणों की एक प्रणाली (system of equations) के कई समाधान हो सकते हैं। इसी तरह, एक arithmetic circuit के भी कई समाधान हो सकते हैं। हालांकि आमतौर पर, हम केवल दिए गए समाधान को सत्यापित करने में रुचि रखते हैं। हमें एक arithmetic circuit के लिए सभी समाधान खोजने की आवश्यकता नहीं है।

Boolean बनाम Arithmetic Circuit

नीचे दी गई तालिका दिखाती है कि Boolean circuits और arithmetic circuits कैसे भिन्न हैं, लेकिन ध्यान रखें कि वे एक witness को मान्य करने के समान उद्देश्य को पूरा करते हैं:

कुछ परिस्थितियों में कम वेरिएबल्स का उपयोग करने की सुविधा के अलावा, arithmetic circuits और Boolean circuits वे उपकरण हैं जो एक ही काम को पूरा करते हैं — यह साबित करना कि आपके पास NP में किसी समस्या का witness है।

प्रारंभिक उदाहरण a + b = c पर लौटना

आइए ऊपर दिए गए हमारे उदाहरण पर फिर से विचार करें: समीकरण a + b = c का प्रतिनिधित्व करने के लिए एक Boolean circuit लिखना, जहाँ हमें c = 12 दिया गया है। एक Boolean circuit के लिए, हमें a, b, और c को बाइनरी में एनकोड करने की आवश्यकता है, जिसके लिए (इस उदाहरण में) प्रत्येक के लिए 4 बिट्स की आवश्यकता होती है। कुल मिलाकर, हमारे पास circuit के 12 इनपुट्स हैं। तुलना के लिए, arithmetic circuit को केवल 3 इनपुट्स की आवश्यकता होती है: a, b, और c। इनपुट्स की संख्या में कमी और समग्र circuit के आकार का छोटा होना ही वह कारण है जिससे हम ZK अनुप्रयोगों (applications) के लिए arithmetic circuits का उपयोग करना पसंद करते हैं।

समीकरणों की प्रणालियों और arithmetic circuits के बीच समानताएं

Boolean circuits में हमेशा एक ऐसा एक्सप्रेशन (expression) होता है जो witness के संतुष्ट होने पर true या false लौटाता है।

उदाहरण के लिए, यदि हमारे पास signals $x$, $y$, और $z$ का एक सेट है, और हम $x$ और $y$ के योग (sum) को $5$ होने के लिए constrain करना चाहते हैं, तो हमें इसके लिए एक अलग समीकरण की आवश्यकता है। हम जिस भी तरह से z को constrain करना चाहेंगे, उसका अपना अलग समीकरण होगा।

यह प्रदर्शित करने के लिए कि arithmetic circuits और Boolean circuits समतुल्य हैं, हम बाद में दिखाएंगे कि किसी भी Boolean circuit को arithmetic circuit में बदला जा सकता है। यह दर्शाता है कि यह साबित करने के उद्देश्य से कि किसी एजेंट के पास P या NP में किसी समस्या का witness है, इनका उपयोग interchangeably किया जा सकता है।

सभी P समस्याएं NP समस्याओं का एक सबसेट (subset) हैं

जैसा कि पिछले chapter on P vs NP में चर्चा की गई है, witness को मान्य करने के लिए computation आवश्यकताओं के संदर्भ में सभी P समस्याएं NP समस्याओं का एक सबसेट हैं, इसलिए हम आगे बढ़ते हुए केवल NP समस्याओं का संदर्भ देंगे, इस समझ के साथ कि इसमें P शामिल है।

हमारा निष्कर्ष यह है कि यदि NP में किसी समस्या के किसी भी समाधान को एक Boolean circuit के साथ मॉडल किया जा सकता है, तो NP (या P) में किसी समस्या के किसी भी समाधान को एक arithmetic circuit के साथ मॉडल किया जा सकता है।

लेकिन इससे पहले कि हम उनकी समतुल्यता (equivalence) का प्रदर्शन करें, हम NP में समस्याओं के समाधानों को मॉडल करने के उदाहरण प्रदान करेंगे ताकि हमें यह समझ (intuition) मिल सके कि arithmetic circuits का उपयोग कैसे किया जाता है।

Arithmetic circuits के उदाहरण

हमारे पहले उदाहरण में, हम ऑस्ट्रेलिया के लिए अपनी 3-coloring समस्या को फिर से हल करते हैं। दूसरे में, हम यह प्रदर्शित करते हैं कि एक सूची (list) को क्रमबद्ध (sorted) साबित करने के लिए एक arithmetic circuit का उपयोग कैसे करें।

उदाहरण 1: Arithmetic Circuit के साथ 3-coloring को मॉडल करना

जब हमने 3-coloring को मॉडल करने के लिए एक Boolean circuit का उपयोग किया था, तो प्रत्येक क्षेत्र (territory) में 3 Boolean variables थे - प्रत्येक रंग के लिए एक - जो यह दर्शाता था कि उस देश को वह रंग सौंपा गया है या नहीं। फिर हमने यह सुनिश्चित करने के लिए constraints जोड़े कि प्रत्येक क्षेत्र में ठीक एक रंग हो (color constraints) और यह लागू करने के लिए constraints जोड़े कि आसन्न (adjacent) क्षेत्रों को एक ही रंग न मिले (boundary constraints)।

Arithmetic circuits का उपयोग करके इस समस्या को मॉडल करना आसान है क्योंकि हम तीन Boolean variables के बजाय प्रत्येक क्षेत्र को उनके रंगों को मॉडल करने के लिए संभावित मानों $\set{1, 2, 3}$ के साथ एक सिंगल signal असाइन कर सकते हैं। हम संख्याओं को स्वेच्छा से (arbitrarily) रंग असाइन कर सकते हैं, जैसे blue = 1, red = 2, और green = 3।

प्रत्येक क्षेत्र के लिए, हम सिंगल कलर constraint को इस प्रकार लिखते हैं:

Copy
0 === (1 - x) * (2 - x) * (3 - x)

यह लागू करने के लिए कि प्रत्येक क्षेत्र का ठीक एक रंग हो। उपरोक्त constraint केवल तभी संतुष्ट हो सकती है जब x, 1, 2, या 3 हो।

3-Coloring Australia

याद करें कि ऑस्ट्रेलिया के छह क्षेत्र हैं:

• WA = West Australia
• SA = South Australia
• NT = Northern Territory
• Q = Queensland
• NSW = New South Wales
• V = Victoria

WA = 1 कहना “पश्चिम ऑस्ट्रेलिया को नीला रंग दें” कहने के बराबर है। इसी तरह, WA = 2 का अर्थ है कि पश्चिम ऑस्ट्रेलिया को “लाल” दिया गया था, और WA = 3 का अर्थ है कि “हरा” दिया गया था।

प्रत्येक क्षेत्र के लिए हमारा कलर constraint (प्रत्येक क्षेत्र को नीला, लाल या हरा होने के लिए बाध्य करना) यह हो जाता है:

Copy
1) 0 === (1 - WA) * (2 - WA) * (3 - WA)
2) 0 === (1 - SA) * (2 - SA) * (3 - SA)
3) 0 === (1 - NT) * (2 - NT) * (3 - NT)
4) 0 === (1 - Q) * (2 - Q) * (3 - Q)
5) 0 === (1 - NSW) * (2 - NSW) * (3 - NSW)
6) 0 === (1 - V) * (2 - V) * (3 - V)

अब हम यह लागू करना चाहते हैं कि पड़ोसी क्षेत्रों का रंग समान न हो। इसे पूरा करने का एक तरीका पड़ोसी क्षेत्र के signals को गुणा (multiply) करना है और यह सुनिश्चित करना है कि गुणनफल (product) एक “स्वीकार्य” (acceptable) है। पड़ोसी क्षेत्रों x और y के लिए निम्नलिखित तालिका पर विचार करें:

यदि दो signals (पड़ोसी क्षेत्रों) की संख्या (रंग) समान है, तो उनका गुणनफल $\set{1,4,9}$ में से एक होगा, जो ऊपर लाल संख्याएं हैं। यदि x और y को 1, 2, या 3 होने के लिए constrain किया गया है, और x और y एक दूसरे के बराबर नहीं हैं, तो गुणनफल xy, $\set{2, 3, 6}$ में से एक होगा। इसलिए, यदि xy = 2 या xy = 3 या xy = 6 है, तो हम इस असाइनमेंट को स्वीकार करते हैं क्योंकि इसका मतलब है कि दो पड़ोसियों के अलग-अलग रंग हैं।

प्रत्येक पड़ोसी क्षेत्र x और y के लिए, हम यह लागू करने के लिए कि वे एक दूसरे के बराबर नहीं हैं, निम्नलिखित constraint का उपयोग कर सकते हैं:

Copy
0 === (2 - xy) * (3 - xy) * (6 - xy)

उपरोक्त समीकरण तभी और केवल तभी संतुष्ट होता है जब गुणनफल xy 2, 3, या 6 के बराबर हो।

बाउंड्री constraints (सीमा प्रतिबंध) बॉर्डर्स के माध्यम से पुनरावृति (iterating) करके और पड़ोसी क्षेत्रों की प्रत्येक जोड़ी के बीच बाउंड्री constraints को लागू करके बनाए जाते हैं जैसा कि नीचे दिया गया वीडियो दर्शाता है:

अब हम बाउंड्री constraints दिखाते हैं:

Copy
Western Australia and South Australia:
7) 0 === (2 - WA * SA) * (3 - WA * SA) * (6 - WA * SA)

Western Australia and Northern Territory
8) 0 === (2 - WA * NT) * (3 - WA * NT) * (6 - WA * NT)

Northern Territory and South Australia
9) 0 === (2 - NT * SA) * (3 - NT * SA) * (6 - NT * SA)

Northern Territory and Queensland
10) 0 === (2 - NT * Q) * (3 - NT * Q) * (6 - NT * Q)

South Australia and Queensland
11) 0 === (2 - SA * Q) * (3 - SA * Q) * (6 - SA * Q)

South Australia and New South Wales
12) 0 === (2 - SA * NSW) * (3 - SA * NSW) * (6 - SA * NSW)

South Australia and Victoria
13) 0 === (2 - SA * V) * (3 - SA * V) * (6 - SA * V)

Queensland and New South Wales
14) 0 === (2 - Q * NSW) * (3 - Q * NSW) * (6 - Q * NSW)

New South Wales and Victoria
15) 0 === (2 - NSW * V) * (3 - NSW * V) * (6 - NSW * V)

दोनों को मिलाकर, हम ऑस्ट्रेलिया के लिए एक वैध 3-coloring होने को साबित करने के लिए पूर्ण arithmetic circuit देखते हैं:

Copy
// color constraints
0 === (1 - WA) * (2 - WA) * (3 - WA)
0 === (1 - SA) * (2 - SA) * (3 - SA)
0 === (1 - NT) * (2 - NT) * (3 - NT)
0 === (1 - Q) * (2 - Q) * (3 - Q)
0 === (1 - NSW) * (2 - NSW) * (3 - NSW)
0 === (1 - V) * (2 - V) * (3 - V)

// boundary constraints
0 === (2 - WA * SA) * (3 - WA * SA) * (6 - WA * SA)
0 === (2 - WA * NT) * (3 - WA * NT) * (6 - WA * NT)
0 === (2 - NT * SA) * (3 - NT * SA) * (6 - NT * SA)
0 === (2 - NT * Q) * (3 - NT * Q) * (6 - NT * Q)
0 === (2 - SA * Q) * (3 - SA * Q) * (6 - SA * Q)
0 === (2 - SA * NSW) * (3 - SA * NSW) * (6 - SA * NSW)
0 === (2 - SA * V) * (3 - SA * V) * (6 - SA * V)
0 === (2 - Q * NSW) * (3 - Q * NSW) * (6 - Q * NSW)
0 === (2 - NSW * V) * (3 - NSW * V) * (6 - NSW * V)

हमारे पास Boolean circuit की तरह ही 15 constraints हैं, लेकिन वेरिएबल्स (signals) की संख्या 1/3 रह गई है। प्रत्येक क्षेत्र के लिए 3 Boolean variables के बजाय, हमारे पास प्रत्येक क्षेत्र के लिए एक signal है। बड़े circuits के लिए, जटिलता और स्थान में यह कमी काफी महत्वपूर्ण (substantial) हो सकती है।

उदाहरण 2: किसी List (सूची) को Sorted (क्रमबद्ध) साबित करना

संख्याओं की एक सूची [a₁, a₂, ..., aₙ] को देखते हुए, हम कहते हैं कि सूची “क्रमबद्ध” (sorted) है यदि aₙ ≥ aₙ₋₁ ≥ … a₃ ≥ a₂ ≥ a₁ है। दूसरे शब्दों में, अंत से शुरुआत तक जाने पर, संख्याएँ non-increasing (बढ़ नहीं रही) हैं।

हमारा लक्ष्य एक ऐसा arithmetic circuit लिखना है जो यह सत्यापित करे कि सूची क्रमबद्ध है।

ऐसा करने के लिए, हमें एक ऐसे arithmetic circuit की आवश्यकता है जो दो signals के लिए a ≥ b को व्यक्त करे। यह पहली नज़र में जितना लगता है उससे कहीं अधिक जटिल हो जाता है क्योंकि arithmetic circuits केवल समानता, जोड़ और गुणा की अनुमति देते हैं, तुलना (comparison) की नहीं।

लेकिन मान लीजिए कि हमारे पास ऐसा “ग्रेटर देन या इक्वल टू” circuit था - इसे GTE(a,b) कहें। तब हम लगातार सूची तत्वों (consecutive list elements) की प्रत्येक जोड़ी की तुलना करने के लिए circuits का निर्माण करेंगे: GTE(aₙ, aₙ₋₁), ..., GTE(a₃, a₂), GTE(a₂, a₁), और यदि वे सभी संतुष्ट हैं, तो सूची क्रमबद्ध है।

$≥$ ऑपरेटर के बिना दो दशमलव संख्याओं (decimal numbers) की तुलना करने के लिए, हमें पहले एक ऐसे arithmetic circuit की आवश्यकता होती है जो संख्या के लिए एक प्रस्तावित बाइनरी प्रतिनिधित्व (binary representation) को मान्य करता है, इसलिए हम पहले बाइनरी नंबरों के बारे में थोड़ा सा विषयांतर (detour) करते हैं।

पूर्व-आवश्यकता (Prerequisite): Binary encoding

हम बाइनरी नंबरों को सबस्क्रिप्ट (subscript) 2 के साथ लिखते हैं। उदाहरण के लिए, 11₂ 3 है और 101₂ 5 है। प्रत्येक 1 और 0 को बिट (bit) कहा जाता है। हम कहते हैं कि सबसे बायां बिट most significant bit (MSB) है और सबसे दायां बिट least significant bit (LSB) है।

जैसा कि हम जल्द ही दिखाएंगे, दशमलव में रूपांतरण के दौरान, most significant bit को सबसे बड़े गुणांक (coefficient) से गुणा किया जाता है और least significant bit को सबसे छोटे गुणांक से गुणा किया जाता है। इसलिए यदि हम चार बिट बाइनरी नंबर को b₃b₂b₁b₀ के रूप में लिखते हैं, तो b₃ MSB है और b₀ LSB है।

नीचे दिया गया वीडियो 1101₂ को 13 में बदलने की प्रक्रिया को दर्शाता है:

जैसा कि वीडियो में दिखाया गया है, एक चार बिट बाइनरी नंबर को निम्नलिखित सूत्र के साथ एक दशमलव संख्या v में परिवर्तित किया जा सकता है:

v = 8b₃ + 4b₂ + 2b₁ + b₀

इसे इस प्रकार भी लिखा जा सकता है:

v = 2³b₃ + 2²b₂ + 2¹b₁ + 2⁰b₀

उदाहरण के लिए, 1001₂ = 9, 1010₂ = 10, इत्यादि। एक सामान्य n बिट बाइनरी नंबर के लिए, रूपांतरण (conversion) है:

v = 2ⁿ⁻¹b₃ + ... + 2¹b₁ + 2⁰b₀

हम दशमलव संख्या को बाइनरी में बदलने के तरीके पर चर्चा को छोड़ (omit) रहे हैं। अभी के लिए, यदि पाठक बाइनरी में बदलना चाहते हैं, तो वे Python के built-in bin फ़ंक्शन का उपयोग कर सकते हैं:

Copy
>>> bin(3)
'0b11'
>>> bin(9)
'0b1001'
>>> bin(10)
'0b1010'
>>> bin(1337)
'0b10100111001'
>>> bin(404)
'0b110010100'

हम निम्नलिखित circuit का उपयोग करके एक arithmetic circuit बना सकते हैं जो यह दावा करता है कि “v एक चार बिट बाइनरी प्रतिनिधित्व b₃, b₂, b₁, b₀ के साथ एक दशमलव संख्या है”:

Copy
8b₃ + 4b₂ + 2b₁ + b₀ === v

// force the "bits" to be zero or one
b₀(b₀ - 1) === 0
b₁(b₁ - 1) === 0
b₂(b₂ - 1) === 0
b₃(b₃ - 1) === 0

Signals b₃, b₂, b₁, b₀ को v का बाइनरी प्रतिनिधित्व होने के लिए बाध्य (constrained) किया जाता है। यदि b₃, b₂, b₁, b₀ बाइनरी नहीं हैं, या v के बाइनरी प्रतिनिधित्व नहीं हैं, तो circuit संतुष्ट नहीं हो सकता है।

ध्यान दें कि signals (v, b₃, b₂, b₁, b₀) के लिए कोई संतुष्ट करने वाला असाइनमेंट नहीं है जहाँ v > 15 हो। अर्थात्, यदि हम b₃, b₂, b₁, b₀ सभी को 1 पर सेट करते हैं (जो कि constraints द्वारा अनुमत अधिकतम मान है), तो योग 15 होगा। इससे अधिक कुछ भी जोड़ना संभव नहीं है। ZK में, इसे कभी-कभी v पर range check (रेंज चेक) कहा जाता है। उपरोक्त circuit न केवल v के बाइनरी प्रतिनिधित्व को प्रदर्शित करता है, बल्कि यह v < 16 को भी लागू (force) करता है।

हम इसे निम्नलिखित circuit में सामान्यीकृत (generalize) कर सकते हैं जो $v < 2^n$ को constrain करता है और हमें v का बाइनरी प्रतिनिधित्व भी देता है:

Copy
2ⁿ⁻¹bₙ₋₁ +...+ 2²b₂ + 2¹b₁ + b₀ === v
b₀(b₀ - 1) === 0
b₁(b₁ - 1) === 0
//...
bₙ₋₁(bₙ₋₁ - 1) === 0

यह कहना कि एक संख्या v अधिकतम n बिट्स के साथ एनकोड की गई है, यह कहने के बराबर है कि $v < 2^n$ है।

$2^n$, $n$ के फ़ंक्शन के रूप में कैसे बदलता है, इसका अंदाज़ा लगाने के लिए निम्नलिखित तालिका पर विचार करें:

ध्यान दें कि बाइनरी में संख्या $2^n$ को स्टोर करने के लिए $2^n - 1$ के मान की तुलना में 1 अधिक बिट की आवश्यकता होती है। जिस संख्या को एनकोड किया गया है उसके बिट्स की संख्या को $n$ बिट्स तक constrain करके, यह उस संख्या को $2^n$ से कम होने के लिए मजबूर करता है।

$2$ की घातों (powers) और उन्हें स्टोर करने के लिए आवश्यक बिट्स की संख्या के बीच के संबंध को याद रखना मददगार है।

• $2^n$ को स्टोर करने के लिए $n + 1$ बिट्स की आवश्यकता होती है। उदाहरण के लिए, $2^0=1_2$, $2^1 = 10_2$, $2^2=100_2$, $2^3=1000_2$ इत्यादि।
• $2^{n-1}$, $2^n$ का आधा है और इसे स्टोर करने के लिए $n$ बिट्स की आवश्यकता होती है।
• $2^n − 1$ को स्टोर करने के लिए $n$ बिट्स की आवश्यकता होती है। यह वह अधिकतम मान है जिसे हम $n$ बिट्स के साथ स्टोर कर सकते हैं, जब सभी बिट्स $1$ पर सेट होते हैं।

यदि हम एक संख्या $n$ लेते हैं और $2^n$ की गणना करते हैं, तो हमें एक $n + 1$ बिट नंबर मिलता है जिसका most significant bit 1 होता है, और बाकी शून्य (zero) होते हैं। नीचे दिए गए उदाहरणों में $n = 3$ है:

$2^{n-1}$, $2^n / 2$ के समान है। चूँकि इसे 2 की किसी घात (power) के रूप में लिखा गया है, इसका अभी भी 1 के MSB और बाकी शून्य के साथ एक बाइनरी नंबर का समान “आकार” (shape) है, लेकिन इसे एनकोड करने के लिए $n + 1$ बिट्स के बजाय $n$ बिट्स की आवश्यकता होगी।

$2^n −1$ एक $n$ बिट नंबर है जिसके सभी बिट्स एक पर सेट हैं।

बाइनरी में ≥ की गणना (Compute) करना

यदि हम एक निश्चित आकार (fixed size), $n$ बिट्स की बाइनरी संख्याओं के साथ काम कर रहे हैं, तो संख्या $2^{n-1}$ विशेष है क्योंकि हम आसानी से यह दावा कर सकते हैं कि एक $n$ बिट बाइनरी नंबर $2^{n-1}$ से बड़ा या उसके बराबर है — या उससे कम है। हम $2^{n-1}$ को “midpoint” (मध्य बिंदु) कहते हैं। नीचे दिया गया वीडियो दर्शाता है कि $n$ बिट नंबर के आकार की तुलना $2^{n-1}$ से कैसे की जाती है:

एक $n$ बिट नंबर के most significant bit की जांच करके, हम बता सकते हैं कि वह संख्या $2^{n-1}$ से बड़ी या उसके बराबर है या $2^{n-1}$ से कम है।

यदि हम $2^{n-1} + \Delta$ की गणना करते हैं और उस योग (sum) के most significant bit को देखते हैं, तो हम जल्दी से बता सकते हैं कि $\Delta$ धनात्मक (positive) है या ऋणात्मक (negative)। यदि $\Delta$ ऋणात्मक है, तो $2^{n-1} + \Delta$ को $2^{n-1}$ से कम होना चाहिए।

यह पता लगाना (Detecting) कि क्या $u \ge v$ है

यदि हम $\Delta$ को $u - v$ से बदल देते हैं तो $2^{n-1} + (u - v)$ का most significant bit हमें बताता है कि $u ≥ v$ है या $u < v$ है।

$2^{n-1} + (u - v)$ में overflow को रोकना

यदि हम $u$ और $v$ को अधिकतम $n - 1$ बिट्स के साथ प्रदर्शित होने के लिए प्रतिबंधित (restrict) करते हैं, जबकि $2^{n-1}$ को $n$ बिट्स के साथ दर्शाया जाता है, तो underflow और overflow नहीं हो सकता। जब $u$ और $v$ दोनों को अधिकतम $n - 1$ बिट्स के साथ दर्शाया जाता है, तो $|u - v|$ का अधिकतम पूर्ण मान (maximum absolute value) एक $n - 1$ बिट नंबर होता है।

हम देखते हैं कि इस स्थिति में $2^{n-1} + (u - v)$ underflow नहीं हो सकता, क्योंकि $2^{n-1}$, $|u - v|$ से कम से कम 1 बिट बड़ा है।

अब overflow की स्थिति पर विचार करें। व्यापकता (generality) को खोए बिना, $n = 4$ के लिए, अर्थात चार बिट संख्याओं के लिए, मध्य बिंदु (midpoint) $2^{n-1} = 2^{4-1} = 8$ या $1000_2$ है। इस स्थिति में, एक 3-बिट नंबर के रूप में $|u - v|$ जो अधिकतम मान ले सकता है, वह $111_2$ है। $1000_2 + 111_2$ जोड़ने पर परिणाम $1111_2$ आता है, जो overflow नहीं है।

$u ≥ v$ के लिए arithmetic circuit का सारांश (Summary), जब $u$ और $v$, $n - 1$ बिट नंबर हैं

• हम $u$ और $v$ को अधिकतम $n - 1$ बिट संख्या होने के लिए constrain करते हैं।
• हम एक arithmetic circuit बनाते हैं जो $n$ बिट्स का उपयोग करके $2^{n-1} + (u - v)$ के बाइनरी प्रतिनिधित्व को एनकोड करता है।
• यदि $2^{n-1} + (u - v)$ का most significant bit 1 है, तो $u \geq v$ होगा और इसके विपरीत।

यह जाँचने के लिए अंतिम arithmetic circuit कि क्या $u \geq v$ है, इस प्रकार है। हम $n = 4$ तय करते हैं जिसका अर्थ है कि $u$ और $v$ को 3-बिट संख्या होने के लिए बाध्य (constrained) किया जाना चाहिए। इच्छुक पाठक इसे $n$ के अन्य मानों के लिए सामान्यीकृत (generalize) कर सकते हैं:

Copy
// u and v are represented with at most 3 bits:
2²a₂ + 2¹a₁ + a₀ === u
2²b₂ + 2¹b₁ + b₀ === v

// 0 1 constraints for aᵢ, bᵢ
a₀(a₀ - 1) === 0
a₁(a₁ - 1) === 0
a₂(a₂ - 1) === 0
b₀(b₀ - 1) === 0
b₁(b₁ - 1) === 0
b₂(b₂ - 1) === 0

// 2ⁿ⁻¹ + (u - v) binary representation
2³ + (u - v) === 8c₃ + 4c₂ + 2c₁ + c₀

// 0 1 constraints for cᵢ
c₀(c₀ - 1) === 0
c₁(c₁ - 1) === 0
c₂(c₂ − 1) === 0
c₃(c₃ − 1) === 0

// Check that the MSB is 1
c₃ === 1

यह दावा करना (Asserting) कि एक सूची (list) क्रमबद्ध (sorted) है

अब जब हमारे पास signals के जोड़े (pairs) की तुलना करने के लिए एक arithmetic circuit है, तो हम सूची में प्रत्येक अनुक्रमिक जोड़ी (sequential pair) के लिए इस circuit को दोहराते हैं और सत्यापित करते हैं कि यह क्रमबद्ध (sorted) है।

उदाहरणों का सारांश (Summary)

हमने दिखाया है कि हम पिछले अध्याय की समस्याओं के समाधान को मॉडल करने वाला एक arithmetic circuit कैसे बना सकते हैं।

अब हम इसे सामान्यीकृत करके कह सकते हैं कि हम एक arithmetic circuit का उपयोग करके NP में किसी भी समस्या को मॉडल कर सकते हैं।

किसी Boolean circuit को arithmetic circuit के साथ कैसे मॉडल किया जा सकता है

किसी भी Boolean circuit को arithmetic circuit का उपयोग करके मॉडल किया जा सकता है। इसका मतलब है कि हम एक Boolean circuit B को एक arithmetic circuit A में बदलने की एक प्रक्रिया (process) को परिभाषित कर सकते हैं, ताकि इनपुट का एक सेट जो B को संतुष्ट करता है, उसे signals के एक सेट में अनुवादित किया जा सके जो A को संतुष्ट करता है। नीचे, हम इस प्रक्रिया के प्रमुख घटकों (key components) की रूपरेखा तैयार करते हैं और एक विशिष्ट Boolean circuit को arithmetic circuit में बदलने के एक उदाहरण पर चलते हैं।

मान लीजिए कि हमारे पास निम्नलिखित Boolean सूत्र है: out = (x ∧ ¬ y) ∨ z। यह सूत्र सत्य है यदि (x true है AND y false है) OR z true है।

हम x, y, और z को arithmetic circuit signals के रूप में एनकोड करते हैं और उन्हें 0 या 1 मान रखने के लिए constrain करते हैं।

निम्नलिखित arithmetic circuit केवल तभी संतुष्ट हो सकता है जब x, y, और z प्रत्येक 0 या 1 हों।

Copy
x(x - 1) === 0
y(y - 1) === 0
z(z - 1) === 0

अब चलिए दिखाते हैं कि Boolean circuit ऑपरेटर्स को arithmetic circuit ऑपरेटर्स में कैसे मैप किया जाए, यह मानते हुए कि इनपुट वेरिएबल्स को 0 या 1 होने के लिए बाध्य (constrained) किया गया है।

AND गेट (gate)

हम Boolean AND t = u ∧ v का arithmetic circuit में इस प्रकार अनुवाद करते हैं:

Copy
u(u - 1) === 0
v(v - 1) === 0
t === uv

t केवल तभी 1 होगा जब u और v दोनों 1 हों, इसलिए यह arithmetic circuit एक AND गेट को मॉडल करता है। u(u - 1) = 0 और v(v - 1) = 0 constraints के कारण, t केवल 0 या 1 हो सकता है।

NOT गेट (gate)

हम Boolean NOT t = ¬u का arithmetic circuit में इस प्रकार अनुवाद करते हैं:

Copy
u(u - 1) === 0
t === 1 - u

जब u 0 होता है तो t 1 होता है और इसके विपरीत। constraint u(u - 1) === 0 के कारण, t केवल 0 या 1 हो सकता है।

OR गेट (gate)

हम Boolean OR t === u ∨ v का arithmetic circuit में इस प्रकार अनुवाद करते हैं:

Copy
u(u - 1) === 0
v(v - 1) === 0
t === u + v - uv

यह OR गेट को क्यों मॉडल करता है, यह देखने के लिए निम्नलिखित तालिका पर विचार करें:

यदि u या v 1 हैं, तो t कम से कम 1 होगा। t को 2 के बराबर होने से रोकने के लिए (जो एक Boolean ऑपरेटर से अमान्य आउटपुट है), हम uv घटाते हैं, जो 1 होगा जब u और v दोनों 1 हों।

ध्यान दें कि ऊपर दिए गए सभी गेट्स के साथ, हमें t(t - 1) === 0 constraint लागू करने की आवश्यकता नहीं है। आउटपुट t निहित रूप से (implicitly) 0 या 1 होने के लिए बाध्य है क्योंकि इनपुट्स के लिए ऐसा कोई असाइनमेंट नहीं है जिसके परिणामस्वरूप t का मान 2 या उससे अधिक हो सके।

out = (x ∧ ¬ y) ∨ z को arithmetic circuit में बदलना (Transforming)

अब जब हमने देखा है कि Boolean circuits के सभी अनुमत (allowed) ऑपरेशन्स का arithmetic circuits में अनुवाद कैसे किया जाता है, तो आइए एक Boolean circuit को एक arithmetic circuit में बदलने का एक उदाहरण देखें।

0 1 constraints बनाएँ

Copy
x(x - 1) === 0
y(y - 1) === 0
z(z - 1) === 0

¬ y को NOT के arithmetic circuit से बदलें (Replace)

out = (x ∧ ¬ y) ∨ z

out = (x ∧ (1 - y)) ∨ z

∧ को AND के arithmetic circuit से बदलें

out = (x ∧ (1 - y)) ∨ z

out = (x(1 - y)) ∨ z

∨ को OR के arithmetic circuit से बदलें

out = (x(1 - y)) ∨ z

out = (x(1 - y)) + z - (x(1 - y))z

out = (x ∧ ¬ y) ∨ z के लिए हमारा अंतिम arithmetic circuit है:

Copy
x(x - 1) === 0
y(y - 1) === 0
z(z - 1) === 0
out === (x(1 - y)) + z - (x(1 - y))z

यदि वांछित (desired) हो, तो हम अंतिम समीकरण को सरल (simplify) कर सकते हैं:

Copy
out === (x(1 - y)) + z - ((x(1 - y))z)
out === x - xy + z - ((x - xy)z)
out === x - xy + z - (xz - xyz)

out === x - xy + z - xz + xyz

हम अर्थ में किसी बदलाव के बिना arithmetic circuit को इस प्रकार भी लिख सकते हैं:

Copy
x² === x
y² === y
z² === z
out === x - xy + z - xz + xyz

सारांश (Summary)

यदि NP में प्रत्येक समस्या के समाधान को एक Boolean circuit के साथ मॉडल किया जा सकता है और प्रत्येक Boolean circuit को एक समतुल्य (equivalent) arithmetic circuit में बदला जा सकता है, तो इसका अर्थ यह है कि NP में प्रत्येक समस्या के समाधान को एक arithmetic circuit के साथ मॉडल किया जा सकता है।

व्यवहार में, ZK डेवलपर्स Boolean circuits की तुलना में arithmetic circuits का उपयोग करना पसंद करते हैं क्योंकि, जैसा कि ऊपर दिए गए उदाहरणों में दिखाया गया है, उन्हें समान कार्य को पूरा करने के लिए आमतौर पर कम वेरिएबल्स की आवश्यकता होती है।

एक Boolean circuit की गणना करने और फिर उसे एक arithmetic circuit में बदलने की कोई आवश्यकता नहीं है। हम सीधे एक arithmetic circuit के साथ NP समस्या के समाधान को मॉडल कर सकते हैं।

अगले कदम (Next steps)

हमने इस लेख में दो बहुत महत्वपूर्ण विवरणों पर सरसरी तौर पर नज़र (glossed over) डाली है। कुछ अन्य चुनौतियाँ मौजूद हैं जिनका समाधान करने की आवश्यकता है। उदाहरण के लिए:

• हमने इस बात पर चर्चा नहीं की कि हमने arithmetic circuit के लिए signals को स्टोर करने के लिए किस डेटाटाइप (datatype) का उपयोग किया और हम addition या multiplication के दौरान overflow को कैसे संभालते हैं।
• हमारे पास सटीकता (precision) खोए बिना 2/3 मान व्यक्त करने का कोई तरीका नहीं है। हम जो भी fixed point या floating point प्रतिनिधित्व चुनते हैं, उसमें राउंडिंग की समस्याएँ (rounding issues) होंगी।

इन समस्याओं से निपटने के लिए, arithmetic circuits की गणना finite fields पर की जाती है: गणित की एक शाखा जहाँ सभी addition और multiplication एक अभाज्य संख्या (prime number) के मॉड्यूलो (modulo) से किए जाते हैं।

Finite field arithmetic में नियमित (regular) arithmetic से कुछ आश्चर्यजनक अंतर हैं जो मॉड्यूलो (modulo) ऑपरेटर द्वारा पेश किए गए हैं, इसलिए अगला अध्याय इनका विस्तार से पता लगाएगा।

RareSkills के साथ और जानें

हमारी मुफ़्त ZK Book में Zero Knowledge Proofs के बारे में और जानें। यह ट्यूटोरियल उस पुस्तक का एक अध्याय है।

अभ्यास की समस्याएँ (Practice Problems)

1. एक arithmetic circuit बनाएँ जो signals x₁, x₂, …, xₙ लेता है और यदि कम से कम एक signal 0 है तो संतुष्ट होता है।

2. एक arithmetic circuit बनाएँ जो signals x₁, x₂, …, xₙ लेता है और यदि सभी signals 1 हैं तो संतुष्ट होता है।

3. एक बाइपार्टाइट ग्राफ (bipartite graph) एक ऐसा ग्राफ है जिसे दो रंगों से इस तरह रंगा जा सकता है कि कोई भी दो पड़ोसी नोड्स समान रंग साझा न करें। यह दिखाने के लिए एक arithmetic circuit योजना तैयार करें कि आपके पास एक ग्राफ के 2-coloring का वैध witness है। Hint (संकेत): 2-coloring के साथ काम करने से पहले इस ट्यूटोरियल में दी गई योजना को समायोजित (adjusted) करने की आवश्यकता है।

4. एक arithmetic circuit बनाएँ जो k को x, y, या z में से अधिकतम (maximum) होने के लिए constrain करता है। अर्थात, यदि x अधिकतम मान है तो k, x के बराबर होना चाहिए, और यही बात y और z के लिए भी लागू होती है।

5. एक arithmetic circuit बनाएँ जो signals x₁, x₂, …, xₙ लेता है, उन्हें बाइनरी होने के लिए constrain करता है, और यदि कम से कम एक signal 1 है तो 1 आउटपुट करता है। Hint: यह जितना दिखता है उससे कहीं अधिक पेचीदा (trickier) है। आपने पहले दो समस्याओं में जो सीखा है उसे संयोजित (combining) करने और NOT गेट का उपयोग करने पर विचार करें।

6. यह निर्धारित करने के लिए एक arithmetic circuit बनाएँ कि क्या कोई signal v दो की घात (power of two - 1, 2, 4, 8, आदि) है। Hint: एक arithmetic circuit बनाएँ जो v के बाइनरी प्रतिनिधित्व को एनकोड करने के लिए signals के एक अन्य सेट को constrain करता है, फिर उन signals पर अतिरिक्त प्रतिबंध (restrictions) लगाएं।

7. एक arithmetic circuit बनाएँ जो Subset sum problem को मॉडल करता है। पूर्णांकों (integers) का एक सेट दिए जाने पर (मान लें कि वे सभी गैर-ऋणात्मक (non-negative) हैं), यह निर्धारित करें कि क्या कोई ऐसा सबसेट (subset) है जिसका योग दिए गए मान $k$ के बराबर है। उदाहरण के लिए, सेट $\set{3,5,17,21}$ और $k = 22$ दिए जाने पर, एक सबसेट $\set{5, 17}$ है जिसका योग $22$ है। बेशक, यह आवश्यक नहीं है कि एक सबसेट सम समस्या (subset sum problem) का समाधान हो ही।

   Hint

   
   एक "स्विच" का उपयोग करें जो 0 या 1 है यदि कोई संख्या सबसेट का हिस्सा है या नहीं।

8. कवरिंग सेट समस्या (covering set problem) एक सेट $S = \set{1, 2, …, 10}$ और $S$ के कई अच्छी तरह से परिभाषित सबसेट्स के साथ शुरू होती है, उदाहरण के लिए: $\set{1, 2, 3}$, $\set{3, 5, 7, 9}$, $\set{8, 10}$, $\set{5, 6, 7, 8}$, $\set{2, 4, 6, 8}$, और यह पूछती है कि क्या हम $S$ के अधिकतम $k$ सबसेट ले सकते हैं ताकि उनका यूनियन (union) $S$ हो। ऊपर दी गई उदाहरण समस्या में, $k = 4$ के लिए उत्तर true है क्योंकि हम $\set{1, 2, 3}$, $\set{3, 5, 7, 9}$, $\set{8, 10}$, $\set{2, 4, 6, 8}$ का उपयोग कर सकते हैं। ध्यान दें कि प्रत्येक समस्या के लिए, हम जिन सबसेट्स के साथ काम कर सकते हैं वे शुरुआत में ही निर्धारित कर दिए जाते हैं। हम स्वयं सबसेट्स का निर्माण नहीं कर सकते हैं। यदि हमें $\set{1,2,3}$, $\set{4,5}$ $\set{7,8,9,10}$ सबसेट्स दिए गए होते तो कोई समाधान नहीं होता क्योंकि संख्या $6$ सबसेट्स में नहीं है।

   दूसरी ओर, यदि हमें $S = \set{1,2,3,4,5}$ और सबसेट्स $\set{1}, \set{1,2}, \set{3, 4}, \set{1, 4, 5}$ दिए गए होते और पूछा जाता कि क्या इसे $k = 2$ सबसेट्स से कवर किया जा सकता है, तो कोई समाधान नहीं होता। हालांकि, यदि $k = 3$ होता तो एक वैध समाधान $\set{1, 2}, \set{3, 4}, \set{1, 4, 5}$ होता।

   हमारा लक्ष्य किसी दिए गए सेट $S$ और $S$ के सबसेट्स की परिभाषित सूची के लिए यह साबित करना है कि क्या हम सबसेट्स का एक ऐसा सेट चुन सकते हैं जिसका यूनियन $S$ हो। विशेष रूप से, सवाल यह है कि क्या हम इसे $k$ या उससे कम सबसेट्स के साथ कर सकते हैं। हम यह साबित करना चाहते हैं कि हम जानते हैं कि इस समस्या को एक arithmetic circuit के रूप में एनकोड करके कौन से $k$ (या उससे कम) सबसेट्स का उपयोग करना है।

मूल रूप से 23 अप्रैल, 2024 को प्रकाशित