The following question are for P and NP problems. When does a problem belong to
ID: 3770175 • Letter: T
Question
The following question are for P and NP problems. When does a problem belong to P-Class and when it belong to NP Class? Give two P-Class problems, and give . NP-Class problems which no one knows belonging to P-class or not. Give the time complexities of each, respectively. Suppose that A is a problem belonging to P-Class and B is a problem belonging to NP-Class. Does A belong to NP-Class? Does B belong to P-Class? Let A be a problem satisfying the following conditions: any problem in NP-Class can be reduced to A in polynomial time, and A is an NP-complete problem. What class does A belong to?Explanation / Answer
a).
P Class : A problem to which deterministic polynomial time algo is possible , that is P class problem.
NP Class : For any problem non deterministic polynomial time algo is possible, that is NP class problem.
b).
P Class example : Linear Search O(n), Matrix Multiplication O(n^3), LCS O(n^2), Minimum Spanning TreeO(n^2)
NP Class : traveling salesperson problem, Hamiltonian, sum of subset problem
c).
A can belong to NP class
B can not belong to P class
d). NP Complete
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.