Some common examples of NP-complete problems include:

  1. Traveling Salesman Problem (TSP): Given a list of cities and the distances between them, find the shortest possible route that visits each city exactly once and returns to the starting city.

  2. Knapsack Problem: Given a set of items with associated values and weights, determine the most valuable combination of items that can be included in a knapsack of limited capacity.

  3. Boolean Satisfiability Problem (SAT): Given a boolean formula in conjunctive normal form (a combination of AND and OR operations), determine if there exists an assignment of truth values to the variables that makes the formula true.

  4. Graph Coloring Problem: Given an undirected graph, assign colors to its vertices in such a way that no two adjacent vertices have the same color, using the fewest possible number of colors.

  5. Subset Sum Problem: Given a set of integers and a target sum, determine if there exists a subset of the integers whose elements sum to the target.

  These are just a few examples, but there are many other problems that fall under the NP-complete category. NP-complete problems are generally considered difficult to solve efficiently, as no known polynomial-time algorithms exist for them.