P and NP

Question 1

Describe P class

Answer 1

Problems that belong to class P are those for which an algorithm can find a solution in polynomial time, specifically in
O(n^k) time, where
n is the input size and
k is a constant.

Question 2

Describe the NP class

Answer 2

Problems for which a potential solution can be verified in polynomial time but not necessarily found in polynomial time.

Example: The Traveling Salesman Problem (TSP). Given a set of cities and the distances between them, finding the shortest possible route that visits each city exactly once and returns to the origin city is an NP problem.

Question 3

Describe the NP Complete problem

Answer 3

NP-Complete problems are the hardest problems in NP for which no efficient solution has been found. If any one of them is solved efficiently, all problems in NP can be solved efficiently.

Question 4

Describe the NP Hard Class.

Answer 4

Problems that are at least as hard as the hardest problems in NP but might not be in NP themselves.