Question:
Which of the following problems is in P?
Which of the following problems is in P?
Show Hint
N/A
Updated On: May 3, 2025
- Matrix multiplication
- Graph isomorphism
- Discrete logarithm
- Knapsack problem
Hide Solution
Verified By Collegedunia
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.
Was this answer helpful?
0
0
Top Questions on Computational Complexity
Questions Asked in AP PGECET exam
- Given \( x_0 \neq 0 \), the iteration \[ x_{n+1} = \frac{1}{2} \left( -\frac{9}{x_n} + x_n \right), n \geq 0 { is a} \]
- AP PGECET - 2025
- Numerical Methods
- Suppose \( \sum_{n=1}^{\infty} a_n (x - 2)^n \) is convergent at \( x = -5 \), then it need not be convergent on which interval?
- AP PGECET - 2025
- Convergence tests
- The set of all critical points of the function \( f(x) = |x^2 - 1| \) on \( [-2, 2] \) is ...........
- AP PGECET - 2025
- Calculus
The surface integral \( \int_S x^2 \, dS \) over the upper hemisphere
\[ z = \sqrt{1 - x^2 - y^2} \]
with radius 1 is ..........- AP PGECET - 2025
- Calculus
- Consider the system of equations:
\[ x + 2y - z = 3 \\ 2x + 4y - 2z = 7 \\ 3x + 6y - 3z = 9 \]
Which of the following statements is true about the system?
- AP PGECET - 2025
- Linear Algebra
View More Questions