Question:
Which of the following problems cannot be solved in polynomial time by a deterministic Turing machine (i.e. is widely conjectured not to be in \(P\))?
निम्नलिखित में से किस समस्या को डिटर्मिनिस्टिक ट्यूरिंग मशीन द्वारा बहुपद समय (Polynomial time) में हल नहीं किया जा सकता (अर्थात् \(P\) में नहीं माना जाता)?
Options:
- 0/1 Knapsack Problem
- Fractional Knapsack Problem
- Single-source Shortest Paths
- Minimum Spanning Tree
- 0/1 नैपसैक समस्या
- फ्रैक्शनल नैपसैक समस्या
- सिंगल-सोर्स शॉर्टेस्ट पाथ
- मिनिमम स्पैनिंग ट्री
Correct Answer: a)
Explanation:
The 0/1 Knapsack Problem is an NP-complete decision problem (pseudo-polynomial dynamic programming solution, but exponential in the number of bits of capacity). Fractional Knapsack is solved in \(O(n \log n)\) via greedy method (Option a).
0/1 नैपसैक समस्या एक NP-कंप्लीट समस्या है, जबकि फ्रैक्शनल नैपसैक ग्रीडी विधि द्वारा बहुपद समय में हल हो जाती है (विकल्प a)।