Question

Which of the following problems is in P?

• A. Matrix multiplication
• B. Graph isomorphism
• C. Discrete logarithm
• D. Knapsack problem

Hint:

N/A

Answer 1

The Correct Option is A

- Matrix multiplication: This problem is known to be in, as matrix multiplication can be solved in polynomial time with algorithms that have time complexities like \(O(n^3)\), which is polynomial.
- Graph isomorphism: This problem has not been proven to be in , and its classification is still an open question. It is in NP but not known to be solvable in polynomial time.
- Discrete logarithm: This problem is not solvable in polynomial time and is widely considered to be sub-exponential in difficulty. 
- Knapsack problem: The knapsack problem is NP-complete.
Therefore, the correct answer is 1. Matrix multiplication.