Another interesting example is the isomorphism of graphs, that is, whether two graphs are isomorphic is determined by graph theory. The intuitive condition for two graphs to be isomorphic is that if one graph can overlap another graph by moving vertices, then it is isomorphic. Consider the following two questions:

Graph isomorphism: Is graph G 1 isomorphic to graph G2?

Subgraph isomorphism: Is graph G 1 isomorphic to any subgraph of graph G2?

The subgraph isomorphism problem is NPC, and the graph isomorphism problem is generally considered to be neither P nor NPC, although it is obviously NP problem. This is a typical example, which is considered difficult, but it is not an NPC problem.

The easiest way to prove that a problem is NPC is to prove that it belongs to NP first, and then turn it into a problem called NPC. Therefore, before learning transformation skills, it is very useful to be familiar with different types of NPC problems. The following table lists some famous NPC problems expressed by decisive propositions:

Boolean satisfiability problem: (Boolean satisfiability problem) (SAT)

N-word puzzle (Huarong Road Problem): (N-word puzzle)

Knapsack problem: (knapsack problem)

Hamilton cycle problem: (Hamilton cycle problem)

Traveling Salesman Problem: (Traveling Salesman Problem)

Subgraph isomorphism problem: (subgraph isomorphism problem)

Subsets and problems: (Subsets and problems)

Grouping problem: (small group problem)

Vertex covering problem: (vertex covering problem)

Independent vertex set problem: (independent set problem)

Graph coloring problem (see four-color theorem): (graph coloring problem)

For more examples of NPC problems, please refer to the NP complete problem list (English version).

On the right are some NPC problems and the transformation flow chart to prove that they are NPC problems. In the flow chart, the arrow represents the process of changing from what problem to another problem. It should be noted that this diagram does not represent the mathematical relationship of these problems. In fact, any two problems that are essentially NPC can be transformed in polynomial time, which only shows that researchers can change the order of the problems more simply.

Usually, there seems to be only some differences in the narrative of a P and NPC problem. For example, the 3SAT problem (the restricted version of the SAT problem) is still an NPC problem, but the 2SAT problem with more restrictions is a P problem (NL- complete problem to be exact), and the MAX 2SAT problem with loose conditions becomes an NPC problem. Deciding whether a graph can be filled with two colors is a P problem, but a three-color graph is an NPC problem, even if we limit it to a plane graph. It is easy to determine whether a graph is cyclic or dichotomous (at the level of logarithmic space), but finding a maximum bipartite graph or maximum cyclic subgraph is NPC. Finding the optimal solution of the fixed percentage packing problem can be solved in polynomial time, but finding the optimal solution is NPC.