एक अधिकतम एंटीथिन का सत्यापन
आदेश सिद्धांत में, एक एंटीचिन (स्पेंपर परिवार / अव्यवस्था) एक आंशिक रूप से आदेशित सेट का एक सबसेट है, इस संपत्ति के साथ कि कोई दो तत्व एक दूसरे के साथ तुलनीय नहीं हैं। एक अधिकतम एंटीथिन एंटीथिन है जो ठीक से दूसरे एंटीथिन में निहित नहीं है। का पावर सेट लेते हैं$\{1,2,\ldots, n\}$हमारे आंशिक रूप से आदेशित सेट के रूप में, यहाँ आदेश समावेश द्वारा दिया गया है। फिर मेरा सवाल है, इस आंशिक रूप से गढ़े हुए सेट के किसी भी एंटीचिन के लिए, क्या कोई बहुपद-कालिक एल्गोरिथ्म है (सम्मान के साथ)$n$) यह सत्यापित करने के लिए कि यह एंटिचैन वास्तव में "अधिकतम" है? दूसरे शब्दों में, किसी भी सबसेट की पुष्टि करना$\{1,2,\ldots, n\}$या तो इसमें निहित है, या इसमें एंटीचिन से कुछ सेट है। यहां इस तरह के एल्गोरिथ्म में किसी भी एंटीचिन के लिए बहुपद रन-टाइम होना चाहिए ।
अद्यतन : स्पष्ट करने के लिए, यहां मैं सत्यापन एल्गोरिथ्म के पैरामीटर के रूप में हमारे एंटीचिन के आकार का इलाज करूंगा। दूसरे शब्दों में, मेरा सवाल यह है: क्या एक सत्यापन एल्गोरिथ्म मौजूद है, जिसका रन-टाइम बहुपद है$n$ तथा $m$, कहां है $m$एंटीचिन का आकार है। जब हमारे एंटीचिन का आकार$m$ में घातीय है $n$फिर ऐसा एल्गोरिथ्म तुच्छ है (बस उन तत्वों की एक-एक करके तुलना करना); लेकिन जब दिए गए एंटिचैन में ओ (पाली (एन)) आकार होता है, तो यह मेरी रुचि का मामला है। उदाहरण के लिए, जब एंटीचिन द्वारा दिया जाता है$\{\{1\}, \ldots, \{n\}\}$, हम निश्चित रूप से जानवर बल तुलना करने के लिए नहीं है।
जवाब
रिमार्क। मूल रूप से मैंने इसका पूरा समाधान होने का दावा किया था, लेकिन यह गलत था, जैसा कि एमिल ने टिप्पणियों में दिखाया है। हालाँकि, यह तर्क निम्न कमजोर संस्करण साबित होता है।
मैं यह साबित कर सकता हूं कि एक इनपुट परिवार के लिए निर्णय लेना सह-एनपी-पूर्ण है $A$ चाहे कोई सेट हो $S$ कि सभी सेट में असंबंधित है $A$। मैं ऐसे परिवारों को अधिकतम कहूँगा। इससे पता चलता है कि किसी भी संभव बहुपद समय एल्गोरिथ्म का शोषण करना चाहिए कि इनपुट परिवार एक एंटीचिन है, पहले से ही रैखिक आकार के इनपुट के लिए। मेरी कमी सैट से है।
एक CNF दिया $\Psi$ पर $n$ चर, हम इसे एक परिवार में बदलते हैं $A$ ऊपर $2n$ तत्व, ऐसे $A$ अधिकतम है अगर और केवल अगर $\Psi$असंतोषजनक में। $2n$ तत्व जोड़े में आएंगे, जिन्हें मैं दर्शाता हूं $i$ तथा $i'$।
हर जोड़ी के पूरक में निहित है$A$ निम्न पर ध्यान दिए बगैर $\Psi$, तोह फिर $\overline{11'}\in A$, $\overline{22'}\in A$,, ... $\overline{nn'}\in A$।
इसके अलावा, हर खंड के लिए हम एक सेट जोड़ते हैं$A$ ऐसा है कि अगर $x_i$ इस खंड में, सेट समाहित है $i$, जबकि अगर $\bar x_i$ इस खंड में, सेट समाहित है $i'$। उदाहरण के लिए, खंड$(x_i\vee \bar x_j)$ सेट जोड़ता है $ij'$ सेवा मेरे $A$।
मान लीजिए $\Psi$संतोषजनक है। फिर एक संतोषजनक मूल्यांकन के लिए$x$निर्धारित करें $S$ ऐसा है कि $i\in S$ अगर $x_i$ गलत है और $i'\in S$ अगर $x_i$सच हैं। यह जाँच करने के लिए सीधे आगे है$S$ के किसी भी तत्व के साथ संबंध में नहीं है $A$।
लगता है कि $A$अधिकतम नहीं है। एक सेट ले लो$S$ किसी भी तत्व के संबंध में नहीं है $A$। परिभाषित$x_i$ अगर सच हो $i\notin S$ और अगर झूठ $i'\notin S$, अन्यथा मनमाने ढंग से। यह परिभाषा वास्तव में सही है, जैसा कि$\overline{ii'}\in A$ इसका आशय है $i,i'\in S$संभव नहीं है। यह जाँच करने के लिए सीधे आगे है$x$ का एक संतोषजनक मूल्यांकन है $\Psi$।