वैज्ञानिकों के लिए एक खुला पत्र और एनपी-पूर्ण 3-वीवाईपी समस्या के लिए रोमनोव एल्गोरिदम का एक संदर्भ कार्यान्वयन

3-वीवाईपी के लिए रोमानोव बहुपद एल्गोरिथ्म पर पिछले प्रकाशन के बाद से 4.5 महीने बीत चुके हैं।

इस समय के दौरान, व्लादिमीर फेडोरोविच और मैंने साथी वैज्ञानिकों को भेजे जाने वाले लेख का एक संस्करण तैयार किया और साथ ही जावा में इस एल्गोरिदम का एक संदर्भ कार्यान्वयन लागू किया।

वैज्ञानिकों को अनुच्छेद और खुला पत्र

लेख के आधार के रूप में, हमने अंग्रेजी में मौजूदा प्रकाशन लिया, जिससे मैंने पिछले पोस्ट में एक लिंक दिया। वर्तमान संस्करण केवल छोटे परिवर्धन में भिन्न है, जो, हमारी राय में, एल्गोरिथ्म की समझ और प्रदान किए गए साक्ष्य को सरल करना चाहिए। किचिक की सलाह पर , आर्टिकल arXiv.org पर प्रकाशित किया गया था:

गैर-रूढ़िवादी संयोजन मॉडल, निरंकुश संरचनाओं के आधार पर
arxiv.org/abs/1011.3944

आज हमने एक खुला पत्र संकलित किया, जो कुछ वैज्ञानिकों को भेजा गया था जिनके संपर्क पाए गए थे (लिंक के लिए अलेनिरोम का धन्यवाद)। पत्र भी साइट पर प्रकाशित किया गया है, जिसे हमने विशेष रूप से चर्चा के लिए बनाया है:

3-सैट: उपन्यास मॉडल
romvf.wordpress.com/2011/01/19/open-letter

यदि किसी के पास इस विषय में शामिल वैज्ञानिकों के संपर्क हैं, तो कृपया उन्हें यह पत्र भेजें। हम किसी भी प्रतिक्रिया और टिप्पणियों का स्वागत करते हैं।

जावा में संदर्भ कार्यान्वयन

जैसा कि हमने लेख के एक नए संस्करण पर काम किया, हमने जावा में एक संदर्भ कार्यान्वयन लिखने के लिए एक एल्गोरिथ्म का पता लगाया। हमने कर दिखाया! आवेदन का पहला संस्करण हमने 19 नवंबर को एलजीपीएल संस्करण 3 के लाइसेंस के तहत जीथब पर प्रकाशित किया था:

बूलियन 3-SAT समस्या के लिए रोमनोव के बहुपद एल्गोरिथ्म का संदर्भ कार्यान्वयन
github.com/anjlab/sat3

अब यह एक एकल-थ्रेडेड कार्यान्वयन है, जो एक कंसोल एप्लिकेशन है जो DIMACS CNF फ़ाइलों से सूत्र पढ़ता है और यदि सूत्र संभव है तो एक रनिंग सेट को आउटपुट करता है, या यदि सूत्र संभव नहीं है तो संबंधित संदेश जारी करता है। कार्यक्रम एक विस्तृत लॉग रखता है, जिसे एल्गोरिदम को समझने के लिए लेख के पाठकों की मदद करनी चाहिए।

बीज के लिए, यहां आलेख (बाएं) से एक उदाहरण के लिए चल रहे सेट के साथ एक बुनियादी ग्राफ है और 100 (दाएं, क्लिक करने योग्य) के बराबर चर की संख्या के साथ एक सूत्र के लिए:

आवेदन के परिणामों का अधिक विस्तृत विवरण यहां पाया जा सकता है । गीथब और कई विकी पेजों पर एक रीमेक है, जिसमें बताया गया है कि एप्लिकेशन को कैसे चलाना है।

नवीनतम प्रकाशित संस्करण 1.0.3 है। लेकिन HEAD में कई अतिरिक्त अनुकूलन शामिल हैं जो 2 गुना (संस्करण 2.0.0-SNAPSHOT) द्वारा एप्लिकेशन को गति देते हैं।

आगे क्या है

आगे के काम को कई क्षेत्रों में विभाजित किया जा सकता है।

1. लेख को अधिक से अधिक इच्छुक लोगों को दिखाने के लिए इसे लोकप्रिय बनाना।
   
   यहां मुझे हैबर की मदद की उम्मीद है। हम एक वैज्ञानिक पत्रिका में एक लेख प्रकाशित करने पर भी काम करेंगे, अब हमारे पास कई विकल्प हैं।
   
   
2. एक उत्पादक कार्यान्वयन बनाना।
   
   संदर्भ कार्यान्वयन मूल रूप से एल्गोरिदम के संचालन के साथ खुद को परिचित करने में पाठकों की सहायता के रूप में कल्पना की गई थी। यह माना जाता था कि यह किसी भी व्यक्तिगत कंप्यूटर पर काम कर सकता है जहां आप जावा चला सकते हैं। इसे बड़े आयाम की औद्योगिक समस्याओं को हल करने के लिए नहीं बनाया गया है।
   
   एक तरफ, यह एल्गोरिथ्म की कम्प्यूटेशनल जटिलता (O (n ^ 4 * m)) से बाधित होता है, दूसरी ओर, संसाधन सीमाओं द्वारा, विशेष रूप से, रैम में। यहां कई विकास पथ हैं: डेटा संरचनाओं और एल्गोरिदम का अनुकूलन, और एल्गोरिथ्म के समानांतरकरण (कई थ्रेड्स, प्रक्रियाओं, आदि में)।
   
   यदि आपको इसके साथ मदद करने की इच्छा है - लिखिए, हम सहयोग करने के तरीकों की तलाश करेंगे।
   
   
3. लागू समस्याओं का समाधान।
   
   3-एसपी समस्या स्वयं विशुद्ध रूप से सैद्धांतिक है, लेकिन कई अन्य लागू समस्याएं इसके नीचे आती हैं। हालांकि यह व्यक्तिगत अध्ययन का विषय है।