P class, NP class, NP HARD, NP COMPLETE in Hindi

P class

P class उन problems का समूह  होता है जो polynomial time में solve हो जाती है। हम कह सकते है कि वे problems जो polynomial time में deterministic Turing machine द्वारा solve हो जाती है उसे P – Class कहते है।

P class algorithm की complexity O(n^k) होती है जहाँ k constant (नियत)  होता है। यदि problem polynomial time में solve हो जाती है तो उसे tractable कहेंगे और जो problem polynomial time में solve नहीं होती उसे intractable या super – polynomial कहेंगे।

उदहारण के लिए:- 

यहाँ एक array है जिसका size n है और हमें एक n एलिमेंट find करना है। हम इस problem को linear search की help से solve करेंगे जहाँ x या तो found होगा या not found होगा। linear search की time complexity O(n) होगी। जो n number तक search perform कर सकती है।

P class के उदाहरण:-  

2-CNF , searching algorithm , sorting algorithm , prims algorithm ,kruskal algorithm , shortest path problem.

NP CLASS

NP class उन decision problems का set होता है जो polynomial time में non deterministic Turing machine द्वारा solve हो जाती है। NP Class  उन problems को consists करता है जो polynomial time में verifiable हो।

NP class decision problems को non deterministic polynomial time में solve करता है। decision problems का मतलब वे problem जिसका solution ‘Yes’ या ‘No’  में हो और non deterministic मतलब जिसमे हम guess perform करते है अर्थात् अंदाजा लगाते है. जैसे :- Sudoku , Sudoku एक ऐसा game है जिसमे हम guess perform करते है।

NP Class decision problems का एक class है जो claimed answer को check करता है कि वह सही है या नहीं। इसमें हम solution को कैसे ढूंढना है ये हम नहीं बता सकते है पर जो solution verify है वह सही है या नहीं यह कह सकते है।

NP Class के उदाहरण:-  3-SAT , 3-CNF , traveling salesman problem (TSP) , Knapsack problem.

Polynomial reduction

किसी एक problem को दुसरे problem में reduce करना ,  मतलब यदि किसी एक problem को solve करने के लिए दुसरे problem में change किया जाता है और उस problem को change करने में जो time लगता है यदि वह polynomial time O(n^k) हो तो वह polynomial reduction कहलाता है।

उदाहरण (Ex) :- यदि हम problem A को solve करना चाहते है और हमारे पास problem A का solution नहीं है तो हम उसे problem B में Convert कर सकते है। problem A को problem B में convert करने में जो time लगता है यदि वह time polynomial time हो तो उसे polynomial reduction कहते है।

NP Hard

एक problem NP Hard तब कहलायेगी जब NP problem के समूह को polynomial time में reduce कर पाएंगे.

NP Hard problems का NP Class में होना या ना होना जरूरी नहीं होता हैं। NP Hard NP Class के अंदर भी हो सकती है और नहीं भी हो सकती है।

NP HARD Ex :- Turing halting Problem.

NP Complete

NP complete problems वे problems होते है जिन्हें polynomial time में reduce कर सकते है। NP Hard problems के वे problem जो NP Class के अंदर आते है उन problems को NP Complete कहते है।

NP Complete problems जो है वह NP Class की सभी problem से polynomial time में reduce हो जाती है साथ ही साथ उन problems का NP में होना जरूरी होता है।

NP Complete जो है वह NP Hard का subset होता है। NP Hard के वे problems जो NP Class में exists करती हो NP Complete कहलाती है।

NP complete ex :- vertex covering problem

निवेदन:- अगर आपको यह पोस्ट पसंद आई हो तो इसे अपने दोस्तों के साथ share करें. तथा इस पोस्ट को लेकर कोई सवाल हो तो मुझें कमेंट के द्वारा बताइये.