Which of the following problems is in P?
Show Hint
- Matrix multiplication
- Graph isomorphism
- Discrete logarithm
- Knapsack problem
The Correct Option is A
Solution and Explanation
- 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.
Top Questions on Computational Complexity
Questions Asked in AP PGECET exam
The rank of matrix \(\begin{bmatrix} k & -1 & 0 \\[0.3em] 0 & k & -1 \\[0.3em] -1 & 0 & k \end{bmatrix}\) is 2, for \( k = \)
- AP PGECET - 2024
- Rank of a Matrix
If \(A = \begin{bmatrix} 4 & 2 \\[0.3em] -3 & 3 \end{bmatrix}\), then \(A^{-1} =\)
- AP PGECET - 2024
- Inverse of a Matrix
A two-port network is defined by the relation
\(\text{I}_1 = 5V_1 + 3V_2 \)
\(\text{I}_2 = 2V_1 - 7V_2 \)
The value of \( Z_{12} \) is:- AP PGECET - 2024
- Two Port Networks
An induction motor when started on load does not accelerate up to full speed but runs at \({\frac {1}{17}}\)th of the rated speed. The motor is said to be:
- AP PGECET - 2024
- Induction Motor
A 0 to 30 V voltmeter has an error of \(\pm 2\%\) of FSD. What is the range of readings if the voltage is 30V?
- AP PGECET - 2024
- Errors in Measurement