बहुपद समय अनुमान योजना
हम एनपी-पूर्ण समस्याओं के लिए कुछ बहुपद समय समाधान पा सकते हैं जैसे 0-1 नैपसैक समस्या या सबसेट सम समस्या। ये समस्याएं वास्तविक दुनिया में बहुत लोकप्रिय हैं, इसलिए इन समस्याओं से निपटने के कुछ तरीके अवश्य होने चाहिए।
बहुपद समय सन्निकटन योजना (पीटीएएस) अनुकूलन समस्याओं के लिए अनुमानित एल्गोरिदम का एक प्रकार है। 0-1 नैपसैक समस्या के लिए, एक छद्म बहुपद समाधान है, लेकिन जब मान बड़े होते हैं, तो समाधान संभव नहीं होता है। फिर हमें एक पीटीएएस समाधान चाहिए।
कुछ एनपी-पूर्ण समस्याएं जैसे ग्राफ रंग, के-सेंटर समस्या इत्यादि। उनके पास कोई ज्ञात बहुपद समय समाधान नहीं है। पीटीएएस एल्गोरिदम का अनुमान लगाने के लिए उपयोग किया जाता है। ये एल्गोरिदम एक पैरामीटर ε> 0 लेते हैं और अनुमानित करने के लिए हम कम से कम (1 + ε) और अधिकतम (1 - ) करेंगे।
उदाहरण
उदाहरण के तौर पर, यदि हम एक न्यूनतम समस्या चुनते हैं और ε =0.5 लेते हैं, तो PTAS का उपयोग करके समाधान लगभग 1.5 होता है। तो चलने का समय n के संदर्भ में बहुपद होना चाहिए, लेकिन यह के संदर्भ में घातीय हो सकता है।