5
मुझे पता है कि बूलियन संतुष्टि एनपी-पूर्ण है, लेकिन बूलियन अभिव्यक्ति का न्यूनतमकरण/सरलीकरण है, जिसके द्वारा मेरा मतलब है प्रतीकात्मक रूप में एक दी गई अभिव्यक्ति लेना और प्रतीकात्मक रूप, एनपी-पूर्ण में समकक्ष लेकिन सरलीकृत अभिव्यक्ति का उत्पादन करना? मुझे यकीन नहीं है कि संतुष्टि से कम करने के लिए कमी है, लेकिन मुझे लगता है कि शायद वहां है। क्या किसी को वाकई पता है?बूलियन अभिव्यक्तियों का न्यूनतमकरण एनपी-पूर्ण है?
थोड़ा और साफ ढंग से लिखा यह वह कमी हो सकती है जिसे वह ढूंढ रहा था। –
आप और मूल पोस्टर का शायद एनपी-हार्ड मतलब है। जहां तक मैं समस्या का पता लगा सकता हूं एनपी में नहीं जाना जाता है। – starblue
स्टारब्लू: नहीं, हमारा मतलब एनपी पूरा है। एसएटी वास्तव में शास्त्रीय एनपी पूर्ण समस्या है, यानी यह पहली समस्या थी जो एनपी पूर्ण साबित हुई थी, और अन्य सभी सीधे या अप्रत्यक्ष रूप से कम हो गए हैं। वैसे, यह विकिपीडिया लेख में समझाया गया है। –