सबसेट अनुमान एनपी-पूर्ण?

Question

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

एन

संख्या 1 से आप उन्हें देख नहीं सकते एन सिक्के हैं, लेकिन फार्म की उनके बारे में एम तथ्यों दिए गए हैं:

struct Fact 
{ 
    set<int> positions 
    int num_heads 
} 

positions सिक्कों के एक उप-समूह की पहचान करता है, और num_heads उस सबसेट में सिक्के की संख्या है जो सिर हैं।

इन एम तथ्यों को देखते हुए आपको अधिकतम संभवतः सिर के काम करने की आवश्यकता है।

क्या यह समस्या एनपी-पूर्ण है? यदि हां, तो कमी क्या है? यदि नहीं, बहुपद समय समाधान क्या है?

उदाहरण के लिए:

N = 5 
M = 3 
fact1 = { {1, 2}, 1 } // Either coin 1 or coin 2 is a head 
fact2 = { {4}, 0 } // Coin 4 is a tail 
fact3 = { {2, 4, 5}, 2 } // Out of coins 2, 4 and 5, two are heads 

कि तथ्यों से मेल खाता है सबसे सिर के साथ एक विन्यास है:

T H H T H 

तो जवाब 3 सिर है।

Answer 1

मान लें कि आपके पास 3-एसएटी समस्या है। आप उस समस्या में प्रत्येक बूलियन वैरिएबल वी को दो सिक्के में मैप कर सकते हैं। उन्हें 'सत्य (v)' और 'झूठी (v)' कहें। विचार यह है कि यदि 3-एसएटी समस्या के समाधान में v सत्य है, तो 'सत्य (v)' सिर है; अन्यथा 'झूठा (v)' सिर है। हर के लिए V आप सिक्का बाधा जोड़ने

{true(v), false(v)} has 1 heads, and has 1 tails 

इस के बाद, आप सिक्का बाधा

{t/f(l1), t/f(l2), t/f(l3)} has at least 1 heads 

को शाब्दिक एल 1, एल 2, एल 3

l1 or l2 or l3 

के साथ एक 3 सैट खंड अनुवाद कर सकते हैं

जहां टी/एफ (एल 1) या तो 'सत्य (एल 1)' या 'झूठी (एल 1)' है, इस पर निर्भर करता है कि एल 1 सकारात्मक है (नकारात्मक नहीं है) या खंड में नकारात्मक (नकारात्मक) है। हमें सिर्फ यह दिखाने की ज़रूरत है कि 'कम से कम 1 सिर' सिक्का समस्या में लागू किया जा सकता है क्योंकि 'कम से कम 1 सिर' स्पष्ट रूप से स्पष्ट नहीं है। यह निम्नलिखित डिवाइस के साथ किया जा सकता है। सी 1, सी 2, सी 3 को तीन सिक्के होने दें जिसके लिए हम बाधा को कहना चाहते हैं 'उनमें से कम से कम एक सिर है'। तीन अन्य सिक्कों x1, x2, X3 बनाएँ और बाधा

{X1, X2, X3, C1, C2, C3} has 4 heads 

लेकिन x1, x2, X3 के लिए कोई अन्य बाधाओं में डाल दिया। यह बाधा केवल तभी संतुष्ट होती है जब कम से कम सी 1, सी 2, सी 3 सिर हो; सिक्कों X1..3 का उपयोग शेष आवश्यक सिर प्रदान करने के लिए किया जा सकता है।

ध्यान दें कि यह कमी समस्या के "सिर की अधिकतम संख्या" पहलू का उपयोग नहीं करती है; 3-एसएटी फॉर्मूला असंतुष्ट होने पर बुलियन वैरिएबल का प्रतिनिधित्व करने वाले सिक्कों के लिए सिर/पूंछ की स्थिति चुनना असंभव है।

यह आपकी सिक्का समस्या के लिए 3-सैट से बहुपद कमी है, यह दिखाता है कि यह एनपी-हार्ड है। यह दिखाने के लिए कि एनपी-पूर्ण है, बस देखें कि आपकी सिक्का समस्या का समाधान बहुपद समय, क्यूईडी में चेक किया जा सकता है।

Answer 2

One-in-three 3SAT आपकी समस्या के निर्णय संस्करण में तुच्छ रूप से कम हो जाता है (क्या कोई कॉन्फ़िगरेशन मौजूद है?), जो एनपी में मामूली रूप से है।अधिकतम संस्करण एनपी- हार्ड (लेकिन पूरा नहीं हुआ क्योंकि यह निर्णय समस्या नहीं है), यहां तक ​​कि वादा संस्करण जहां एक संतोषजनक कॉन्फ़िगरेशन होना चाहिए: निर्णय में कमी के आउटपुट में जोड़ें एक अतिरिक्त सिक्का जो सभी में दिखाई देता है सबसेट, एक बुरा, अतिरिक्त समाधान बनाना जहां वह सिक्का सिर है और अन्य सभी पूंछ हैं।

Answer 3

सही मिलान से इस समस्या में सीधा कमी आती है - ग्राफ के प्रत्येक चरम के लिए किनारों को सिक्कों के रूप में दर्शाते हैं, एक तथ्य बनाते हैं कि वास्तव में आकस्मिक किनारों में से एक सिर है। मूल ग्राफ में एक सही मिलान मौजूद है अगर केवल तभी सिक्कों में कोई समाधान हो।