💻 computer science

Coverage Games

यह शोध पत्र "कवरेज गेम्स" (coverage games) को प्रस्तुत करता है, जो एक नवीन मल्टी-एजेंट प्लानिंग फ्रेमवर्क है जहाँ कई एजेंटों का संचालन करने वाला एक 'कवरर' (coverer), उद्देश्यों के एक समूह को पूरा करने के लिए एक 'डिसरप्टर' (disruptor) के विरुद्ध प्रतिस्पर्धा करता है, और उनके नियतता (determinacy), उद्देश्य अपघटन (objective decomposition), और गणनात्मक जटिलता (computational complexity) का एक व्यापक सैद्धांतिक विश्लेषण प्रदान करता है।

मूल लेखक: Orna Kupferman (The Hebrew University, School of Computer Science and Engineering, Jerusalem, Israel), Noam Shenwald (The Hebrew University, School of Computer Science and Engineering, Jerusalem, Isra

प्रकाशित 2026-03-24

📖 7 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Orna Kupferman (The Hebrew University, School of Computer Science and Engineering, Jerusalem, Israel), Noam Shenwald (The Hebrew University, School of Computer Science and Engineering, Jerusalem, Israel)

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

मुख्य विचार: "सभी आधारों को कवर करने" का खेल

कल्पना कीजिए कि आप एक संग्रहालय की सुरक्षा करने वाले गार्डों की टीम (कवरर - Coverer) के मैनेजर हैं। आपका लक्ष्य यह सुनिश्चित करना है कि हर एक प्रदर्शनी (ऑब्जेक्टिव्स - Objectives) को अनंत काल तक देखा जाए। हालाँकि, आपका इस पर पूर्ण नियंत्रण नहीं है। वहाँ एक शरारती सूत्रधार (डिसरप्टर - Disruptor) है जो गार्डों को इधर-उधर घुमा सकता है, गलियारों को ब्लॉक कर सकता है, या ध्यान भटकाने के लिए व्याकुलता पैदा कर सकता है।

एक मानक सुरक्षा खेल में, आमतौर पर आपके पास केवल एक गार्ड होता है जो एक चीज़ की निगरानी करता है, या शायद एक गार्ड जो सब कुछ एक साथ देखने की कोशिश करता है।

कवरेज गेम्स (Coverage Games) अलग हैं। यहाँ, आपके पास कई गार्ड्स (एजेंट्स) हैं, लेकिन आपको पहले से यह नहीं पता कि किस गार्ड को कौन सी प्रदर्शनी देखनी चाहिए। आपके पास देखने के लिए 10 प्रदर्शनियों की सूची है, लेकिन केवल 3 गार्ड हैं।

चुनौती: आपको एक ऐसी योजना बनानी होगी जहाँ, सूत्रधार चाहे कितनी भी गड़बड़ी करने की कोशिश करे, हर एक प्रदर्शनी को आपके कम से कम एक गार्ड द्वारा देखा जाए।
ट्विस्ट: आपको हमेशा के लिए यह तय करने की ज़रूरत नहीं है कि गार्ड A प्रदर्शनी 1 को देखेगा और गार्ड B प्रदर्शनी 2 को। असाइनमेंट गतिशील रूप से बदल सकता है। हो सकता है कि गार्ड A कुछ समय के लिए प्रदर्शनी 1 को देखे, फिर प्रदर्शनी 2 पर स्विच हो जाए, जबकि गार्ड B प्रदर्शनी 1 की जिम्मेदारी संभाल ले। जब तक कोई न कोई हर समय सब कुछ देख रहा है, तब तक आप जीत जाते हैं।

दो मुख्य प्रश्न

यह शोध पत्र इस खेल के बारे में दो बड़े सवाल पूछता है:

कवरेज की समस्या (The Coverage Problem): क्या मैनेजर (कवरर) जीतने के लिए कोई रणनीति बना सकता है? (अर्थात, क्या हम यह गारंटी दे सकते हैं कि हर प्रदर्शनी देखी जाए, चाहे सूत्रधार कुछ भी करे?)
व्यवधान की समस्या (The Disruption Problem): क्या सूत्रधार (डिसरप्टर) जीतने के लिए कोई रणनीति बना सकता है? (अर्थात, क्या सूत्रधार ऐसी स्थिति पैदा कर सकता है जहाँ कम से कम एक प्रदर्शनी बिना किसी निगरानी के रह जाए, चाहे मैनेजर गार्डों को कैसे भी घुमाए?)

प्रमुख खोजें ("अहा!" मोमेंट्स)

1. खेल हमेशा "निष्पक्ष" नहीं होता (अनिश्चित/Undetermined)

कई क्लासिक खेलों (जैसे शतरंज) में, एक पक्ष के पास जीतने की रणनीति सुनिश्चित होती है। यदि आप पूरी तरह से खेलते हैं, तो आप जीतेंगे।

कवरेज गेम्स में: ऐसा हमेशा सच नहीं होता। कभी-कभी, मैनेजर जीत की गारंटी नहीं दे सकता, लेकिन सूत्रधार भी जीत की गारंटी नहीं दे सकता। यह एक "डेडलॉक" या गतिरोध है जहाँ परिणाम वास्तविक समय में किए गए विशिष्ट मूव्स पर निर्भर करता है, न कि केवल पहले से बनाई गई रणनीति पर।
उपमा: धुंधले जंगल में टैग (पकड़ने वाला खेल) के खेल की कल्पना करें। पकड़ने वाला (सूत्रधार) धावक (मैनेजर) को पकड़ने की गारंटी नहीं दे सकता क्योंकि धावक पूरी तरह से बच सकता है। लेकिन धावक हमेशा के लिए बचने की गारंटी नहीं दे सकता क्योंकि पकड़ने वाला भाग्यशाली हो सकता है। दोनों के पास 100% काम करने वाली कोई "परफेक्ट" योजना नहीं है।

2. "विभाजन" की समस्या (The "Splitting" Problem)

मैनेजर के लिए सबसे कठिन हिस्सा काम को विभाजित करना है।

उपमा: कल्पना कीजिए कि आपके पास 10 काम (ऑब्जेक्टिव्स) हैं और 2 बच्चे (एजेंट्स) हैं। आप केवल यह नहीं कह सकते कि "बच्चा 1 काम 1-5 करेगा और बच्चा 2 काम 6-10 करेगा" क्योंकि सूत्रधार बच्चे 1 को केवल काम 1 करने में फँसा सकता है।
अंतर्दृष्टि: शोध पत्र दिखाता है कि आप अक्सर खेल शुरू होने से पहले विभाजन का निर्णय नहीं ले सकते। मैनेजर को लचीला होना चाहिए। यदि सूत्रधार गार्डों को किसी विशिष्ट गलियारे की ओर धकेलता है, तो मैनेजर को तुरंत फिर से असाइन करना होगा कि कौन क्या देखेगा। पेपर इन निर्णय बिंदुओं को "फोर्क्स" (Forks) कहता है। जीतने की रणनीति एक 'फोर्क' तक पहुँचने और फिर सूत्रधार द्वारा गार्डों को कहाँ भेजा जाता है, उसके आधार पर कार्यों को गतिशील रूप से विभाजित करने में निहित है।

3. जटिलता: इसे हल करना कितना कठिन है?

लेखकों ने गणना की है कि कंप्यूटर के लिए इन खेलों को हल करना कितना कठिन है।

सामान्य मामला (General Case): यह बहुत कठिन (PSPACE-complete) है। यह एक विशाल भूलभुलैया को हल करने जैसा है जहाँ आपको कई कदम आगे सोचना पड़ता है, और संभावनाओं की संख्या बहुत बढ़ जाती है।
निश्चित संख्या में गार्ड्स: यदि आपके पास केवल गार्डों की एक छोटी, निश्चित संख्या है (जैसे, हमेशा 2 गार्ड), तो समस्या आसान (NP-complete) हो जाती है, लेकिन फिर भी कठिन है।
निश्चित संख्या में कार्य: यदि आपके पास देखने के लिए प्रदर्शनियों की एक छोटी, निश्चित संख्या है, तो यह समस्या बहुत आसान (Polynomial Time) हो जाती है। कंप्यूटर इसे जल्दी से हल कर सकता है।

आश्चर्यजनक तथ्य:
आमतौर पर, कंप्यूटर विज्ञान में, "को-बुची" (Co-Büchi) उद्देश्य (जिसका अर्थ है "इन बुरी चीजों से हमेशा के लिए बचना") "बुची" (Büchi) उद्देश्यों (जिसका अर्थ है "इन अच्छी चीजों पर हमेशा के लिए पहुँचना") की तुलना में संभालना आसान होता है।

इस पेपर में: डिसरप्टर (सूत्रधार) के लिए, जब गार्डों की संख्या निश्चित होती है, तो को-बुची गेम बुची गेम की तुलना में वास्तव में अधिक कठिन होते हैं। यह ऐसा है जैसे सूत्रधार के लिए कुछ गार्डों के होने पर "बचने" के लक्ष्य को रोकने की तुलना में "पहुँचने" के लक्ष्य को रोकना अधिक कठिन होता है।

वास्तविक दुनिया के अनुप्रयोग

यह क्यों मायने रखता है? शोध पत्र सुझाव देता है कि यह ढांचा निम्नलिखित में मदद करता है:

रोबोट स्वार्म्स (Robot Swarms): कल्पना कीजिए कि ड्रोन का एक बेड़ा शहर की गश्त कर रहा है। आप यह सुनिश्चित करना चाहते हैं कि हर पड़ोस की जाँच की जाए। "सूत्रधार" खराब मौसम, ट्रैफ़िक या एक हैकर हो सकता है। सिस्टम को यह जानने की आवश्यकता है कि क्या ड्रोन अराजकता के बावजूद पूरे शहर को कवर कर सकते हैं।
साइबर सुरक्षा (Cybersecurity): आपके पास विभिन्न हैकर हमलों (ऑब्जेक्टिव्स) को रोकने के लिए कई फायरवॉल (एजेंट्स) हैं। हैकर (डिसरप्टर) घुसपैठ करने का रास्ता खोजने की कोशिश करता है। क्या आपका सिस्टम यह गारंटी दे सकता है कि हमले के हर प्रकार को कम से कम एक फायरवॉल द्वारा रोका जाएगा?
ट्रैफ़िक प्रबंधन (Traffic Management): आप यह सुनिश्चित करना चाहते हैं कि शहर से बाहर जाने वाला कम से कम एक मार्ग कभी जाम न हो। "एजेंट्स" ट्रैफ़िक लाइट हैं, और "डिसरप्टर" कारों का प्रवाह है। क्या ट्रैफ़िक लाइटें एक रास्ता खुला रखने के लिए समन्वय कर सकती हैं?

संक्षेप में

कवरेज गेम्स (Coverage Games) अराजक वातावरण में टीम वर्क के बारे में सोचने का एक नया तरीका है। एक व्यक्ति को एक काम सौंपने के बजाय, यह पूछता है: "क्या लचीले श्रमिकों की एक टीम सभी आवश्यक कार्यों को पूरा कर सकती है, भले ही एक परेशान करने वाला व्यक्ति उन्हें भ्रमित करने की कोशिश करे?"

यह पेपर सिद्ध करता है कि हालांकि यह वास्तविक दुनिया की समस्याओं को मॉडल करने का एक शक्तिशाली तरीका है, यह गणितीय रूप से जटिल है। जीतने की कुंजी एक कठोर योजना नहीं, बल्कि एक लचीली रणनीति है जो सही क्षण पर अपनी टीम के प्रयासों को विभाजित करने (Forks) के लिए जानती है ताकि कुछ भी पीछे न छूटे।

यहाँ ओरना कुप्परमैन और नोआम शेनवाल्ड के शोध पत्र "कवरेज गेम्स" (Coverage Games) का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या की परिभाषा

यह शोध पत्र कवरेज गेम्स (CGs) को पेश करता है, जो प्रतिकूल वातावरण (adversarial environments) में मल्टी-एजेंट प्लानिंग के लिए एक नया ढांचा है, जहाँ एक सिस्टम (कवरर - Coverer) कई एजेंटों ( $k$ ) का संचालन करता है लेकिन उनके व्यवहार पर पूर्ण नियंत्रण नहीं रखता या ऐसे वातावरण के साथ इंटरैक्ट करता है जिसमें कई एजेंट शामिल होते हैं।

खिलाड़ी (The Players):
- कवरर (Coverer): $k$ एजेंटों का संचालन करता है। इसका लक्ष्य यह सुनिश्चित करना है कि उद्देश्यों का एक सेट $\beta = \{\alpha_1, \dots, \alpha_m\}$ कवर (covered) हो। एक उद्देश्य तब कवर माना जाता है जब वह $k$ एजेंटों के प्लेज़ (plays) में से कम से कम एक द्वारा संतुष्ट किया जाता है।
- डिसरप्टर (Disruptor): एक प्रतिकूल खिलाड़ी जो एक एकल रणनीति (single strategy) का उपयोग करके सभी $k$ एजेंटों के साथ एक साथ इंटरैक्ट करता है। इसका लक्ष्य कवरर को सभी उद्देश्यों को कवर करने से रोकना है (अर्थात, यह सुनिश्चित करना कि सभी $k$ प्लेज़ में कम से कम एक उद्देश्य असंतुष्ट रहे)।
गेम की संरचना (The Game Structure):
- यह एक गेम ग्राफ $G = \langle V_1, V_2, v_0, E \rangle$ पर खेला जाता है।
- $k$ टोकन $v_0$ से शुरू होते हैं। प्रत्येक एजेंट एक टोकन को नियंत्रित करता है।
- परिणाम $k$ प्लेज़ (पथों) का एक टुपल (tuple) होता है।
- जीतने की स्थिति (Winning Condition): कवरर तब जीतता है यदि $\bigcup_{i=1}^k \text{sat}(\rho_i, \beta) = \beta$ हो, जहाँ $\text{sat}(\rho, \beta)$ प्ले $\rho$ द्वारा संतुष्ट उद्देश्यों का सेट है।
मुख्य अंतर: मानक मल्टी-ऑब्जेक्टिव गेम्स (जहाँ एक एजेंट को सभी उद्देश्यों को संतुष्ट करना होता है) या मानक मल्टी-एजेंट प्लानिंग (जहाँ एजेंट पूरी तरह से नियंत्रित होते हैं) के विपरीत, CGs में आंशिक नियंत्रण (प्रतिकूल वातावरण) और विघटन (उद्देश्यों को एजेंटों के बीच गतिशील रूप से विभाजित किया जा सकता है) शामिल है।
निर्धारणता (Determinacy): एक महत्वपूर्ण सैद्धांतिक निष्कर्ष यह है कि CGs अनिवार्य रूप से निर्धारित (determined) नहीं होते हैं। यह संभव है कि न तो कवरर के पास जीतने वाली कवरेज रणनीति हो और न ही डिसरप्टर के पास जीतने वाली डिस्रप्शन रणनीति हो।

2. कार्यप्रणाली और सैद्धांतिक ढांचा

लेखक इस समस्या का विश्लेषण गेम थ्योरी, ऑटोमेटा थ्योरी और कम्प्यूटेशनल कॉम्प्लेक्सिटी का उपयोग करके करते हैं।

उद्देश्य के प्रकार (Objective Types): अध्ययन ब्यूची (Büchi) (एक सेट को अनंत बार देखना) और को-ब्यूची (co-Büchi) (एक सेट को सीमित बार देखना) उद्देश्यों पर केंद्रित है।
विकोंपनीयता (Decomposability): एक केंद्रीय अवधारणा यह है कि क्या उद्देश्यों के सेट $\beta$ को $k$ एजेंटों के बीच पूर्व-निर्धारित (a-priori) रूप से विभाजित किया जा सकता है। लेखक सिद्ध करते हैं कि सामान्य रूप से, कवरर उद्देश्यों के स्थिर विभाजन के लिए प्रतिबद्ध नहीं हो सकता; विभाजन को गतिशील होना चाहिए, जो डिसरप्टर के मूव्स पर निर्भर करता है।
फोर्क्स (Forks) और $V_{avoid}$ :
- एक फोर्क (fork) वह वर्टेक्स है जहाँ कवरर अलग-अलग उद्देश्यों के उपसमुच्चयों को कवर करने के लिए एजेंटों को अलग-अलग उत्तराधिकारियों (successors) पर विभाजित कर सकता है।
- लेखक $V_{avoid}$ को उन वर्टेक्स के सेट के रूप में परिभाषित करते हैं जिनसे डिसरप्टर गेम को किसी भी फोर्क तक पहुँचे बिना बनाए रखने के लिए मजबूर कर सकता है।
- थ्योरम 3.5 एक रिकर्सिव लक्षण वर्णन स्थापित करता है: कवरर $v$ से जीतता है यदि $v \notin V_{avoid}$ (एक फोर्क तक पहुँच सकता है) OR यदि $v \in V_{avoid}$ और कवरर सबग्राफ $G_{avoid}$ पर एक सिंगल-एजेंट गेम जीत सकता है।
सिंबोलिक रणनीतियाँ (Symbolic Strategies): डिस्रप्शन समस्या (विशेष रूप से को-ब्यूची उद्देश्यों के लिए) के लिए, लेखक स्पष्ट अनंत रणनीतियों के अनुमान की आवश्यकता के बिना, डिस्रप्टिंग रणनीतियों को सिंबॉलिक रूप से वर्णित करने के लिए फेयरनेस रिक्वायरमेंट्स (fairness requirements) और सुपरसेट ऑब्जेक्टिव्स (superset objectives) का उपयोग करते हैं।

3. मुख्य योगदान और परिणाम

A. सैद्धांतिक गुण

अन-डिटरमिनेंसी (Undeterminacy): CGs निर्धारित नहीं होते हैं। ऐसे खेल मौजूद हैं जहाँ दोनों में से किसी के पास भी जीतने वाली रणनीति नहीं होती। यह छोटे उदाहरणों ( $k=2$ एजेंट, $|\beta|=3$ उद्देश्य) के लिए भी सत्य है।
गैर-विकोंपनीयता (Non-Decomposability): कवरर आम तौर पर उद्देश्यों को स्थिर रूप से विभाजित नहीं कर सकता। जीतने वाली रणनीति के लिए अक्सर एजेंटों के बीच उद्देश्यों को विभाजित करने का निर्णय लेने के लिए डिसरप्टर के मूव्स पर प्रतिक्रिया देना आवश्यक होता है।
विशेष मामले:
- यदि $k=1$ , तो समस्या मानक मल्टी-ऑब्जेक्टिव टू-प्लेयर गेम्स में बदल जाती है।
- यदि $k \ge |\beta|$ , तो समस्या $|\beta|$ स्वतंत्र सिंगल-ऑब्जेक्टिव गेम्स में विभाजित हो जाती है (कवरर तभी जीतता है जब वे व्यक्तिगत रूप से प्रत्येक में जीतते हैं)।

B. जटिलता विश्लेषण (Complexity Analysis)

शोध पत्र कवरेज (Coverage) और डिस्रप्शन (Disruption) समस्याओं का व्यापक विश्लेषण प्रदान करता है। जटिलता उद्देश्य के प्रकार (ब्यूची बनाम को-ब्यूची) और इस बात पर निर्भर करती है कि पैरामीटर्स ( $k$ या $|\beta|$ ) फिक्स्ड (fixed) हैं या नहीं।

तालिका 1: जटिलता का सारांश (संयुक्त जटिलता):

समस्या	ब्यूची उद्देश्य (Büchi)	को-ब्यूची उद्देश्य (co-Büchi)
कवरेज (Coverage)	PSPACE-complete	PSPACE-complete
डिस्रप्शन (Disruption)	$\Sigma_2^P$ -complete	$\Sigma_2^P$ -complete

कवरेज समस्या: PSPACE में हल करने योग्य है। हार्डनेस QBF (क्वांटिफाइड बुलियन फॉर्मूला) से रिडक्शन के माध्यम से सिद्ध की गई है।
डिस्रप्शन समस्या: $\Sigma_2^P$ $Σ_{2}^{P}$ (NP के साथ एक co-NP ऑरेकल) में हल करने योग्य है। यह कवरेज से स्पष्ट रूप से आसान है। हार्डनेस 2QBF से रिडक्शन के माध्यम से सिद्ध की गई है।
- नोट: ब्यूची के लिए, डिसरप्टर के पास एक मेमोरीलेस डिस्रप्टिंग रणनीति होती है। को-ब्यूची के लिए, रणनीतियों को मेमोरी की आवश्यकता हो सकती है, लेकिन उन्हें सिंबॉलिक रूप से वर्णित किया जा सकता है।

C. पैरामीटराइज्ड कॉम्प्लेक्सिटी (Parameterized Complexity)

लेखक विश्लेषण करते हैं कि जब गेम ग्राफ $G$ बड़ा होता है, लेकिन $k$ (एजेंट) या $|\beta|$ (उद्देश्य) फिक्स्ड होते हैं, तो जटिलता क्या होती है।

फिक्स्ड पैरामीटर	कवरेज (ब्यूची/को-ब्यूची)	डिस्रप्शन (ब्यूची)	डिस्रप्शन (को-ब्यूची)
फिक्स्ड $k$	NP-complete	NP-complete	$\Sigma_2^P$ -complete
फिक्स्ड $\|\beta\|$	PTIME	PTIME	PTIME

फिक्स्ड $k$ का महत्व:
- कवरेज के लिए, $k$ को फिक्स करने से जटिलता PSPACE से घटकर NP हो जाती है।
- डिस्रप्शन (ब्यूची) के लिए, $k$ को फिक्स करने से जटिलता $\Sigma_2^P$ से घटकर NP हो जाती है।
- डिस्रप्शन (को-ब्यूची) के लिए, $k$ को फिक्स करने से जटिलता कम नहीं होती है; यह $k=2$ के लिए भी $\Sigma_2^P$ -complete बनी रहती है। यह एक मौलिक विषमता को उजागर करता है: को-ब्यूची उद्देश्य, फिक्स्ड एजेंटों के साथ डिस्रप्ट करने में अधिक कठिन होते हैं क्योंकि उन अधिकतम उद्देश्यों के सेट को खोजना कठिन होता जिन्हें एक एजेंट संतुष्ट कर सकता है।
फिक्स्ड $|\beta|$ का महत्व: उद्देश्यों की संख्या को फिक्स करने से सभी मामलों के लिए दोनों समस्याएं PTIME-complete हो जाती हैं, क्योंकि संभावित विभाजनों की संख्या स्थिर हो जाती है।

4. महत्व और अनुप्रयोग

मल्टी-रोबोट सर्विलांस (Multi-Robot Surveillance): यह सुनिश्चित करना कि महत्वपूर्ण स्थानों पर कम से कम एक रोबोट द्वारा अनंत बार जाया जाए, भले ही वातावरण (डिसरप्टर) रास्तों को ब्लॉक कर दे या बाधाएं उत्पन्न कर दे।
साइबर-सुरक्षा (Cyber-Security): यह सुनिश्चित करना कि प्रत्येक संभावित हमले के वेक्टर (attack vectors) को कम से कम एक रक्षा तंत्र द्वारा कम किया जाए, जो एक प्रतिकूल हैकर का मुकाबला करता है।
मल्टी-थ्रेडेड सिस्टम (Multi-threaded Systems): यह सुनिश्चित करना कि शेड्यूलर (डिसरप्टर) के व्यवहार के बावजूद, कम से कम एक प्रक्रिया द्वारा महत्वपूर्ण संसाधनों तक अनंत बार पहुँचा जाए।
ट्रैफिक मैनेजमेंट (Traffic Management): यह सुनिश्चित करना कि कई वाहनों की क्रियाओं के बावजूद कम से कम एक मार्ग अनकंजस्टेड (uncongested) रहे।

5. निष्कर्ष

यह शोध पत्र कवरेज गेम्स को साझा लक्ष्यों और प्रतिकूल वातावरण वाले मल्टी-एजेंट सिस्टम के बारे में तर्क करने के लिए एक कठोर ढांचे के रूप में स्थापित करता है। प्राथमिक योगदान विघटन चुनौती (decomposition challenge) की पहचान करना है: एजेंटों के बीच उद्देश्यों को गतिशील रूप से विभाजित करने की आवश्यकता। लेखक सटीक जटिलता सीमाएं प्रदान करते हैं, यह दिखाते हुए कि जबकि सामान्य समस्या PSPACE-complete है, यह ट्रैक्टेबल (PTIME) हो जाती है यदि उद्देश्यों की संख्या फिक्स हो, और NP-complete हो जाती है यदि एजेंटों की संख्या फिक्स हो (ब्यूची के लिए)। को-ब्यूची उद्देश्यों के लिए डिस्रप्शन समस्या में $\Sigma_2^P$ हार्डनेस का बने रहना (विशेष रूप से फिक्स्ड एजेंटों के साथ) एक नवीन और महत्वपूर्ण सैद्धांतिक अंतर्दृष्टि है।