गणनात्मक जटिलता

कंप्यूटर साइंस में कॉन्सेप्ट्स

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

जटिलता श्रेणियाँ

जटिलता श्रेणियाँ

एक ऐनिमेशन जो पूरी प्रॉब्लम जटिलता स्पेस दिखाता है

एक चित्र जो P प्रॉब्लम स्पेस दिखाता है

Complexity Class -->	P (Polynomial Time)
मतलब	तेज़ और कुशलता से हल योग्य
उदाहरण	सूची को सॉर्ट करना
उपमा	"दस्तावेज़ों को वर्णक्रम में फाइल करना"
मुख्य बिंदु	ये कम्प्यूटेशनल रूप से "आसान" हैं

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

एक चित्र जो P और NP प्रॉब्लम स्पेस दिखाता है

Complexity Class -->	NP (Non-deterministic Polynomial Time)
मतलब	समाधान की जाँच आसान, नया समाधान खोजना कठिन
उदाहरण	Sudoku पहेली की शुद्धता जाँचना
उपमा	"अधूरी जानकारी में खास दस्तावेज़ ढूँढना"
मुख्य बिंदु	वेरिफ़िकेशन "आसान" है, नए समाधान खोजना कठिन

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

एक चित्र जो P, NP, और NP-Complete प्रॉब्लम स्पेस दिखाता है

Complexity Class -->	NP-Complete
मतलब	NP में सबसे कठिन. खास क्योंकि सभी NP को सॉल्व में रिड्यूस होता है
उदाहरण	Traveling salesman problem
उपमा	"जटिल जिग्सॉ पहेली सुलझाना: जाँचना आसान, हल करना कठिन"
मुख्य बिंदु	कोई कुशल समाधान ज्ञात नहीं. मिल जाए तो सभी NP हल हो जाएँगे

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

एक चित्र जो P, NP, NP-Complete, और NP-Hard प्रॉब्लम स्पेस दिखाता है

Complexity Class -->	NP-Hard
मतलब	NP-Complete जितना कठिन या उससे भी ज्यादा
उदाहरण	जटिल निर्भरताओं के साथ ऑप्टिमल शेड्यूलिंग, जिसे वेरिफ़ाई नहीं किया जा सकता
उपमा	"अनेक बाधाओं के साथ मीटिंग का सर्वश्रेष्ठ समय तय करना, जिसे जल्दी वेरिफ़ाई नहीं कर सकते"
मुख्य बिंदु	व्यवहार में हल करना शायद असंभव

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

एक डायग्राम जो लंबे समय से चला आ रहा शोध प्रश्न पूछता है: क्या P=NP?

कंप्यूटर साइंस में कॉन्सेप्ट्स