The first problem proved to be NP-complete was
ASAT, via the Cook-Levin theorem (1971)
BHamiltonian Cycle, by Hamilton himself
CTravelling Salesman, by Dijkstra
Dthe Halting Problem, by Turing in 1936
Answer & Solution
Correct answer: A. SAT, via the Cook-Levin theorem (1971)
Stephen Cook (1971) and independently Leonid Levin proved that SAT — the question of whether a Boolean formula in CNF has a satisfying assignment — is NP-complete. This was the foundational result; every other NP-completeness proof reduces from SAT (or from a problem reduced from SAT). The Halting Problem is undecidable, not NP-complete; Hamilton predates the theory; Dijkstra worked on shortest paths.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined forThe running time and space of Floyd-Warshall on a graph with V vertices and E edges is