Which is a standard NP-complete problem?

• A. Verifying a given solution in polynomial time
• B. Sorting a list
• C. SAT (Boolean satisfiability)
• D. Finding the maximum flow in a network

Answer: (C)

SAT is a classic NP-complete problem because it sits at the intersection of two important ideas: quick verifiability and universal hardness within NP. It’s in NP because, given a proposed truth assignment to the variables, you can evaluate the boolean formula and check whether it’s satisfied in time polynomial in the formula’s size. It’s NP-hard due to Cook’s theorem: any problem in NP can be translated into a SAT instance in polynomial time, such that solving that SAT instance would solve the original problem. Put together, SAT is both in NP and as hard as any problem in NP, so it’s NP-complete.

The other options don’t fit this combination: verifying a solution quickly describes a property of NP, not a specific NP-complete problem; sorting and maximum flow have polynomial-time algorithms and are in P, so they are not NP-complete.