डीएए - कुक की प्रमेय
स्टीफन कुक ने अपने पेपर "प्रमेय साबित करने की प्रक्रिया की जटिलता" में चार प्रमेय प्रस्तुत किए। ये प्रमेय नीचे दिए गए हैं। हम समझते हैं कि इस अध्याय में कई अज्ञात शब्दों का उपयोग किया जा रहा है, लेकिन हमारे पास विस्तार से सब कुछ पर चर्चा करने की कोई गुंजाइश नहीं है।
स्टीफन कुक द्वारा चार प्रमेय निम्नलिखित हैं -
प्रमेय -1
अगर एक सेट S स्ट्रिंग्स को कुछ गैर-नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय के भीतर स्वीकार किया जाता है S P-reducible to {DNF tautologies} है।
प्रमेय -2
निम्नलिखित सेट जोड़े में एक दूसरे के लिए पी-रिड्यूसबल हैं (और इसलिए प्रत्येक में एक ही बहुपद की डिग्री है): {tautologies}, {DNF tautologies}, D3, {सब-ग्राफ जोड़े}।
प्रमेय -3
किसी के लिए TQ(k) प्रकार का Q, $ \ mathbf {\ frac {T_ {Q} (k)} {\ frac {\ sqrt {k}} {(log \: k) ^ 2}}} $ अनबाउंड है
वहां एक है TQ(k) प्रकार का Q ऐसे कि $ T_ {Q} (k) \ leqslant 2 ^ {k (log \: k) ^ 2} $
प्रमेय -4
यदि स्ट्रिंग्स के सेट S को समय के भीतर एक गैर-नियतात्मक मशीन द्वारा स्वीकार किया जाता है T(n) = 2n, और अगर TQ(k) प्रकार का एक ईमानदार (वास्तविक समय गणना योग्य) कार्य है Q, फिर एक स्थिरांक है K, इसलिए S समय के भीतर एक नियतात्मक मशीन द्वारा पहचाना जा सकता है TQ(K8n)।
सबसे पहले, उन्होंने बहुपद समय पुनर्विकास के महत्व पर जोर दिया। इसका मतलब है कि अगर हमारे पास एक समस्या से एक बहुपद समय में कमी है, तो यह सुनिश्चित करता है कि दूसरी समस्या से किसी भी बहुपद समय एल्गोरिथ्म को पहली समस्या के लिए एक समान बहुपद समय एल्गोरिथ्म में परिवर्तित किया जा सकता है।
दूसरा, उन्होंने निर्णय की समस्याओं के वर्ग एनपी पर ध्यान केंद्रित किया जो एक गैर-नियतात्मक कंप्यूटर द्वारा बहुपद समय में हल किया जा सकता है। ज्यादातर असाध्य समस्याएं इसी वर्ग की हैं, एनपी।
तीसरा, उन्होंने साबित किया कि एनपी में एक विशेष समस्या में संपत्ति है कि एनपी में हर दूसरी समस्या को बहुपत्नी रूप से कम किया जा सकता है। यदि बहुपद समय एल्गोरिथ्म के साथ संतोषजनकता समस्या को हल किया जा सकता है, तो एनपी में हर समस्या को बहुपद समय में भी हल किया जा सकता है। अगर एनपी में कोई भी समस्या असाध्य है, तो संतोषजनक समस्या अचूक होनी चाहिए। इस प्रकार, संतुष्टि की समस्या एनपी में सबसे कठिन समस्या है।
चौथा, कुक ने सुझाव दिया कि एनपी में अन्य समस्याएं संतोष की समस्या के साथ साझा हो सकती हैं जो एनपी के सबसे कठिन सदस्य होने की संपत्ति है।