締切済み

３彩色問題について質問です。

2012/11/10 21:24

下記の問題が解けません。説明をよろしくお願いします。 P=NPとする。３彩色可能グラフがあるとして、有効な３彩色を作れる多項時間アルゴリズムが存在することを示せ。ヒント：P=NPの仮定はグラフが多項時間内で３彩色可能なグラフかどうかを決定できることを示唆する。しかしP=NPの仮定にはこのテストがどのようになされるかしめされていない。大事なのはそのテストが探せるということを証明することである。