Which of the following is NOT an NP-Complete problem?

To determine which problem is NOT NP-Complete, we analyze each option:

1. Traveling Salesman Problem (TSP): This is a classic NP-Complete problem. It involves finding the shortest route that visits all cities exactly once and returns to the start. It is known to be NP-Complete because no polynomial-time algorithm is known, and it can be reduced to other NP-Complete problems.

2. Boolean Satisfiability Problem (SAT): This is the first problem proven to be NP-Complete. It asks whether a given Boolean formula can be made true by assigning values to its variables. It is NP-Complete because it is both in NP and NP-hard.

3. Shortest Path Problem: This problem can be solved efficiently using algorithms like Dijkstra's or Bellman-Ford. These algorithms run in polynomial time, so the problem is in P. Since P is a subset of NP, but not all problems in NP are in P, this problem is not NP-Complete.

4. More than one of the above: This option is incorrect because only one problem (Shortest Path) is not NP-Complete. The others are NP-Complete.

5. None of the above: This option is incorrect because the Shortest Path Problem is not NP-Complete, so there is at least one non-NP-Complete problem in the list.

Therefore, the correct answer is the Shortest Path Problem.

हिन्दी उत्तर:

एक ऐसी समस्या जो NP-पूर्ण नहीं है, उसे खोजने के लिए, हम प्रत्येक विकल्प का विश्लेषण करते हैं:

1. ट्रैवलिंग सेल्समैन समस्या (TSP): यह एक शास्त्रीय NP-पूर्ण समस्या है। यह उन सभी शहरों को ठीक एक बार दौरा करने वाले छोटे से छोटे मार्ग को खोजने का काम करती है और शुरुआती बिंदु पर लौटती है। यह NP-पूर्ण है क्योंकि कोई बहुपद समय वाला एल्गोरिदम ज्ञात नहीं है, और इसे अन्य NP-पूर्ण समस्याओं में घटाया जा सकता है।

2. बूलियन सैटिस्फायबिलिटी समस्या (SAT): यह पहली समस्या थी जिसे NP-पूर्ण साबित किया गया था। यह पूछती है कि क्या एक दिए गए बूलियन सूत्र को अपने चरों को मूल्य देकर सच बनाया जा सकता है। यह NP-पूर्ण है क्योंकि यह न केवल NP में है बल्कि NP-कठिन भी है।

3. शॉर्टेस्ट पाथ समस्या: यह समस्या डायक्स्ट्रा या बेलमन-फोर्ड एल्गोरिदम का उपयोग करके दक्षता से हल की जा सकती है। ये एल्गोरिदम बहुपद समय में चलते हैं, इसलिए समस्या P में है। चूंकि P NP का एक उपसमुच्चय है, लेकिन NP में सभी समस्याएँ P में नहीं होती हैं, इसलिए यह समस्या NP-पूर्ण नहीं है।

4. उपरोक्त में से एक से अधिक: यह विकल्प गलत है क्योंकि केवल एक समस्या (शॉर्टेस्ट पाथ) NP-पूर्ण नहीं है। अन्य विकल्प NP-पूर्ण हैं।

5. उपरोक्त में से कोई नहीं: यह विकल्प गलत है क्योंकि शॉर्टेस्ट पाथ समस्या NP-पूर्ण नहीं है, इसलिए सूची में कम से कम एक गैर-NP-पूर्ण समस्या है।

इसलिए, सही उत्तर शॉर्टेस्ट पाथ समस्या है।