Classes of Computational Complexity

Question 1

P: Problems that can be SOLVED in O(N^c)

Answer 1

Problems that can be solved in polynomial time.

Any computational problem that can be solved in polynomial time (or better, of course) is considered a member of P. In other words, given a computational problem, if there exists a polynomial time algorithm that solves the problem—where we would need to formally prove that the algorithm does indeed always provide an optimal solution to the problem—we would classify the problem as class P.

P: Problems that can be SOLVED in O(N^c)

Question 2

NP: Problems that can be verified in O(N^c)

Non-deterministic Polynomial

Answer 2

Problems that can be verified in polynomial time.

can verify the answer for correctness in polynomial time is considered a member of NP

NP: Problems that can be verified in O(N^c)

P is a subset of NP

Question 3

P != NP

Answer 3

NP-Hard overlapping with NP.
P is a subset of NP
NP-Complete is intersection of NP-Hard and NP

Question 4

P = NP

Answer 4

P = NP = (NP-Complete) are all in the same set/subset

NP-Hard is in NP but also has area outside. NP is a subset of NP-Hard

Question 5

What are the four classes of computational problems?

Answer 5

P: there exists a polynomial time algorithm that solves the problem
NP: Problems verified in polynomial time (P is subset of NP)
NP-Complete: The intersection of NP and NP-Hard
NP-Hard: Problems at least as hard as the hardest problem in NP

Question 6

Which are true?
A. All problems in P can be solved in polynomial time

B. All problems in NP can be verified in polynomial time

C. All problems in NP can be solved in polynomial time

D. All problems in P can be verified in polynomial time

Answer 6

A,