If problem X <=_p Y and Y <=_p Z, then by transitivity of polynomial-time reduction:
Polynomial-time reduction <=_p is a transitive relation. If X reduces to Y and Y reduces to Z, then X reduces to Z in polynomial time.
Which of the following problems belong to CLASS P (solvable in deterministic polynomial time)?
MST (Prim/Kruskal O(E log V)), Shortest Path (Dijkstra O((V+E)log V)), and 2-SAT (Implication graph O(V+E)) are all in P. 3-SAT is NP-Complete.
Which of the following problems are NP-COMPLETE?
3-SAT, Vertex Cover, and Hamiltonian Cycle are NP-Complete. Eulerian Circuit is in P (degree checks).
Which of the following statements regarding NP-COMPLETENESS are CORRECT?
Statement 1, 2, 3 are core theorems of NP-completeness. Statement 4 is false because all NP problems (including NPC) can be verified in polynomial time.
Which of the following graph properties can be checked in LINEAR TIME O(V + E)?
Checking bipartiteness, cycle detection, and topological sorting run in O(V + E) linear time. Maximum clique is NP-Hard.