बूलियन संतुष्टि - एल्गोरिदम

Question

मेरे पास एक बूलियन सूत्र है: (x_ {1} या x_ {2}) और (x_ {3} या x_ {4}) और ..... और (x_ {2r-1 } या x_ {2r}), जहां x_ {i} सेट से संबंधित है: {p_ {1}, p_ {2}, ... p_ {99}, ~ p_ {1}, ~ p_ { 2}, ... ~ p_ {99}} और मुझे यह निर्धारित करना है कि x_ {i} के कुछ मानों के लिए सूत्र सही है या नहीं।

मुझे पता है कि यह सामान्य रूप से कठिन है। लेकिन क्या कोई विशेष तरीका है कि मैं इस विशेष समस्या को कर सकता हूं? अब तक मैंने बैकट्रैकिंग की कोशिश की है - यह रिकर्सन में है, मैं हर संभव चर (0 या 1 इतने सारे नहीं) को हर संभावित चर और प्रत्येक चर के लिए प्रतिस्थापित करता हूं, जिसे अभी तक मूल्य नहीं मिला है, यह सचमुच सच है। इससे पहले कि मैं रिकर्सन में गहराई से जाऊं, मैं सूत्र को छेड़छाड़ करता हूं (यहां तक ​​कि जब प्रत्येक चर को मूल्य नहीं मिलता है) और यदि यह गलत है, तो मैं गहरा नहीं जाता। लेकिन यह बहुत धीमी है। कोई विचार? मैं मदद के लिए बहुत आभारी होंगे।

Answer 1

यदि आपके पास प्रति या दो खंड हैं, तो आपके पास 2-SAT है, जिसमें एक रैखिक-समय समाधान है।