अवलोकन

1

क्लास P, नियतात्मक ट्यूरिंग मशीन (deterministic Turing machine) में बहुपद समय (polynomial time) में तय की जा सकने वाली समस्याओं का वर्ग है, और क्लास NP उन समस्याओं का वर्ग है जिसमें, यदि हाँ (Yes) होने का प्रमाण (जिसे Witness कहा जाता है) दिया जाता है, तो बहुपद समय में Witness की वैधता को जाँचा जा सकता है (इसे सत्यापन कहा जाता है)। चूँकि बहुपद समय में तय की जा सकने वाली समस्याओं को बहुपद समय में सत्यापित किया जा सकता है, यह स्पष्ट है कि P⊆NP, लेकिन यह स्पष्ट नहीं है कि P, NP का उचित उपसमुच्चय (proper subset) है या नहीं। अभी तक कोई प्रमाण नहीं है, लेकिन कई शोधकर्ताओं का मानना है कि P≠NP है। और यह अनुमान कि यह क्लास P और क्लास NP समान नहीं हैं, "P≠NP अनुमान" कहलाता है।