एनपी पूरा पर विकिपीडिया प्रविष्टि से:एनपी-पूर्ण होने वाली पहली एनपी-पूर्ण समस्याओं को कैसे दिखाया गया था?
"सबसे आसान तरीका साबित होता है कि कुछ नई समस्या एन पी-सम्पूर्ण साबित होता है कि यह एनपी में है पहला है, और फिर करने के लिए कुछ ज्ञात एन पी-सम्पूर्ण समस्या को कम करने यह "
मैं बहुत यकीन है कि मैं इस बात को समझ कर रहा हूँ: अगर मैं एक समस्या है, मैं दिखा सकते हैं कि यह एनपी पूरा है अगर मैं:
दिखाने (एक समाधान है कि यह एनपी में है पर समस्या पर बहुपद समय में सत्यापित की जा सकती है -deterministic ट्यूरिंग मशीन)
दिखाएँ कि एक समस्या पहले से ही एनपी पूरा हो जाता नई समस्या के लिए 'कम' किया जा सकता है
तो, मेरे सवाल है, पहली NP- कैसे थे एनपी पूर्ण होने के लिए पूरी तरह से सिद्ध 'साबित'? एक समय में, ज्ञात एनपी-पूर्ण समस्याओं का सेट शून्य होना चाहिए, और इससे उपर्युक्त प्रक्रिया में चरण 2 का सहारा लेना असंभव हो गया होगा।
इससे मुझे लगता है कि सबूत के लिए एक अलग विधि है जिसे मुझे पता नहीं है। ज्ञात बहुपद समय समाधान की कमी के कारण या तो, या शायद पूरी एनपी-पूर्ण संपत्ति कुछ समस्याओं के लिए 'माना जाता है' है। (वास्तव में, यह लिखा है, अगर यह मामला है तो मुझे आश्चर्य नहीं होगा, लेकिन मुझे कुछ गुरु-फीडबैक चाहिए)।
आपके पास चरण 2 पीछे था (मैंने इसे ठीक कर दिया है)। एनपी-पूर्ण समस्या में आपकी समस्या को कम करने के लिए पर्याप्त नहीं है। आपको अपनी नई समस्या में एनपी-पूर्ण समस्या को कम करना होगा। (अन्यथा, आपने वास्तव में नहीं दिखाया है कि आपकी समस्या मूल एनपी-पूर्ण समस्या जितनी मुश्किल है।) – cjm