The description of the 3-Color problem is as follows: Given a graph G, color each vertex in G such that no two adjacent vertices have the same color. The question is whether it is possible to achieve this using 3 colors.
First, we prove that this problem is an NP problem. Obviously, if a solution is given, we only need to traverse each node and check if its color is different from its adjacent nodes, which can be done in polynomial time. Therefore, the 3-Color problem is an NP problem.
Next, we prove that the 3-Color problem is NP-hard by reducing SAT to the 3-Color problem. That is, given any SAT, we can convert it to the 3-Color problem in polynomial time. In fact, through the following proof, we can ultimately know that the 3-Color problem and SAT problem are actually completely equivalent.
First, we know that SAT is equivalent to the circuit problem. That is, any SAT can be transformed into an equivalent circuit. We use the circuit as an intermediary to prove that the 3-Color problem can be used to construct a circuit, which demonstrates the equivalence between the 3-Color problem and the circuit problem, and thus the equivalence between the 3-Color problem and the SAT problem.
First, we define the 3 colors we want to use as T, F, and N. T represents true, F represents false, and N represents another color (such as neutral). Assuming our input variable is P, we first try to connect P and N to make the value of P can only be T or F, thus constructing a boolean variable.
Next, we introduce a new node NOT(P) and try to construct a NOT gate. The method we construct is to first connect NOT(P) with N to make it a boolean variable, and then connect it with P to make it different from the value of P. At this point, when P is true, NOT(P) is false; when P is false, NOT(P) is true.
In this way, we have successfully constructed a NOT gate. Now let's try to construct an OR gate. We introduce three nodes P, Q, and P OR Q, representing two inputs and the output of the OR gate. We first connect P, Q, and P OR Q with N to make them boolean variables, and then connect the nodes as shown in the figure.
When P is true and Q is false, we can see from the figure that P OR Q can only be true. Similarly, when P is false and Q is false, we can see from the figure that P OR Q can only be false.
By doing so, we have successfully used the 3-Color problem to construct a NOT gate and an OR gate. Combining them, we obtain an OR-NOT gate. According to logic circuits, using OR-NOT gates, we can construct all other gates. Therefore, starting from the 3-Color problem, we have constructed electronic logic. Thus, for any circuit problem, I can convert it into a 3-Color problem by substitution; for any 3-Color problem, I can also convert it into a circuit problem by substitution. The substitution process can obviously be done in polynomial time. Therefore, we have proved the equivalence between the 3-Color problem and the SAT problem, that is, the 3-Color problem is NP-complete.