If a problem A is polynomial-time reducible to problem B (A <=_p B), and problem B is in P, then problem A is:
If A <=_p B and B is solvable in polynomial time, we can solve A in polynomial time by transforming A to B and solving B. Thus A is in P.
Which of the following problems is known to be in CLASS P?
Minimum Spanning Tree is solvable in O(E log V) polynomial time by Prim's or Kruskal's algorithm. 3-SAT, TSP, and Vertex Cover are NP-Complete.
Which of the following problems is NP-COMPLETE?
3-SAT is NP-Complete. In contrast, 2-SAT (implication graph SCCs), Shortest Path (Dijkstra), and Eulerian Circuit (degree checks) are all in P.
The VERTEX COVER problem asks if there exists a subset of k vertices that touches every edge in graph G. Vertex Cover is known to be:
Vertex Cover is one of Karp's 21 classic NP-Complete problems.
The INDEPENDENT SET problem asks if there exists a subset of k vertices such that no two vertices in the subset are adjacent. Independent Set is:
Independent Set is NP-Complete. It is directly dual to the Vertex Cover problem (S is an Independent Set iff V \ S is a Vertex Cover).