3 色問題（3-Color）の説明は以下の通りです：グラフ G が与えられた場合、G の各頂点に色を塗り、隣接する 2 つの頂点の色が異なるようにする必要があります。上記の要件を満たすために 3 つの色を使用できるかどうかを尋ねます。
まず、この問題が NP 問題であることを証明します。明らかに、解が与えられた場合、各ノードを走査し、その隣接ノードの色が一致しているかどうかをチェックするだけで、解が正しいかどうかを判断できます。この操作は明らかに多項式時間で完了するため、3 色問題は NP 問題です。
次に、SAT を 3 色問題に変換することによって、3 色問題が NP 困難であることを証明します。つまり、任意の SAT が与えられた場合、多項式時間でそれを 3 色問題に変換できます。実際、以下の証明によって、3 色問題と SAT 問題が実際に完全に等価であることがわかります。
まず、SAT が実際に回路問題と等価であることを知っています。つまり、任意の SAT に対して、そのブール式は等価な回路に変換できます。私たちは回路を中間として使用し、3 色問題を回路で構成することによって、3 色問題と回路問題の等価性を示し、それによって SAT 問題との等価性を示します。
まず、私たちが使用する 3 つの色をそれぞれ T、F、N とします。ここで、T は真を表し、F は偽を表し、N は他の中立的な色（例えば中性）を表します。入力変数を P とすると、P を N に接続して、P の値が T と F のみになるようにします。つまり、ブール変数を構築します。
次に、新しいノード NOT (P) を導入し、NOT ゲートを構築しようとします。構築方法は、まず NOT (P) を N に接続してブール変数にし、次に NOT (P) を P に接続して、P の値と同じにならないようにします。これにより、P が真の場合、NOT (P) は偽になります。P が偽の場合、NOT (P) は真になります。
これで、NOT ゲートを成功させました。次に、OR ゲートを構築してみましょう。3 つのノード P、Q、P OR Q を導入し、2 つの入力と OR ゲートの出力を表します。まず、P、Q、P OR Q をそれぞれ N に接続してブール変数にし、次に以下の図のように各ノードを接続します。
P が真であり、Q が偽の場合、図から P OR Q は真であることがわかります。同様に、P が偽であり、Q も偽の場合、図から P OR Q は偽であることがわかります。
これにより、3 色問題を使用して NOT ゲートと OR ゲートを構築することに成功しました。これらを組み合わせることで、OR NOT ゲートを得ることができます。論理回路に基づいて、OR NOT ゲートを使用して他のすべてのゲートを構築することができます。したがって、3 色問題から出発して、電子回路を構築しました。したがって、任意の回路問題は、置換によってそれを 3 色問題に変換できます。同様に、任意の 3 色問題も置換によって回路問題に変換できます。置換のプロセスは明らかに多項式時間で完了するため、3 色問題と SAT 問題の等価性を証明しました。つまり、3 色問題は NP 完全です。