The HAMILTONIAN CYCLE problem asks whether a graph contains a closed loop visiting every VERTEX exactly once. Hamiltonian Cycle is:
Hamiltonian Cycle is NP-Complete. In contrast, Eulerian Circuit (visiting every EDGE once) is in P.
For a connected undirected graph, the EULERIAN CIRCUIT problem asks whether there is a closed trail using every EDGE exactly once. This problem is:
An undirected connected graph has an Eulerian circuit if and only if every vertex has an EVEN degree, which can be checked in O(V + E) time (in P).
The SUBSET SUM problem asks if a subset of integers sums to a target value T. Subset Sum is:
Subset Sum is NP-Complete. While it can be solved in pseudo-polynomial time O(n * T) via DP, it is NP-complete with respect to binary input length.
What is a PSEUDO-POLYNOMIAL TIME algorithm?
A pseudo-polynomial algorithm (like 0/1 Knapsack O(n*W)) is polynomial in input magnitude W, but exponential in bit-length log2(W).
If an NP-Complete problem can be solved by an approximation algorithm with approximation ratio rho = 1 in polynomial time, then:
An approximation ratio of 1 means finding the exact optimal solution in polynomial time. Solving an NP-Complete problem exactly in polynomial time implies $P = NP$.