四色問題は1976年に当時のコンピュータで二千数百時間をかけて力ずくで証明されましたが、その後のコンピュータによる証明の追試やアルゴリズムの改良、または実行時間の短縮状況などについて知りたいです。(英語可)

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2004/07/09 23:49:46
  • 終了:--

回答(3件)

id:lobelia No.1

lobelia回答回数600ベストアンサー獲得回数12004/07/10 03:29:27

ポイント25pt

http://www.hatena.ne.jp/1089384586#

四色問題は1976年に当時のコンピュータで二千数百時間をかけて力ずくで証明されましたが、その後のコンピュータによる証明の追試やアルゴリズムの改良、または実行時間の短.. - 人力検索はてな

Kenneth Appel and Wolfgang Haken以降に

発表されたもしくは改良された

四色問題の解法.

専門ではないので,内容までは理解できませんでした.

Robertson, Sanders, Seymour, Thomas, The four-color theorem

http://citeseer.ist.psu.edu/kainen00octonion.html

An Octonion Model for Physics - Kainen (ResearchIndex)

http://citeseer.ist.psu.edu/bar-natan99lie.html

Lie Algebras And The Four Color Theorem (ResearchIndex)

http://citeseer.ist.psu.edu/515365.html

Temperley-Lieb Algebras And The Four-Color Theorem - Kauffman, Thomas (ResearchIndex)

以上は四色問題に関するちゃんとした論文です.

で,ここからは日本語のサイト

トンデモ理論の可能性もありますが,

私にはわかりませんので,

もし,お気に召しませんでしたらポイントは結構です.上記リンクも含めて.

四色問題の簡明な解決

四色問題を解く

ニューラルネットワークで解く4色問題。

同上??

http://www.math.tohoku.ac.jp/~kuroki/SB/#Gardner

スペンサー・ブラウンなんていらない

スペンサー・ブラウンのトンデモ説??

id:another

求めていたのは最初の論文にあるような情報でした。なるほど、Sparc 20で3時間20分ですか。しかし、他に挙げられていたリンクも興味深く読ませていただきました。ありがとうございました。

2004/07/10 14:08:31
id:last_wednesday No.2

last_wednesday回答回数17ベストアンサー獲得回数02004/07/10 06:29:20

ポイント20pt

既出のサイトの通り、1996年にNeil Robertson、 Daniel Sanders、 Paul Seymour、 Robin Thomasによって改良され、

調べる必要のあるパターンが1,936(1,476)から633に減ったようです。

リンク集。

プログラムは見つけられませんでした。

2000年にAshay Dharwadkerにより行われた、より新しい証明の試みのようです。

正しいものかどうかはわかりませんでした。

http://www.angelfire.com/mi4/proof/

On Dharwadker's Magnificent Proof

概説と批評。

http://www.nasaexplores.com/extras/maps/maps_home_2002.html

NASAexplores: Map Coloring - A Mathematical Challenge

ついでにNASAの地図塗り分けページ。

id:another

ありがとうございます。Dharwadker解は謎ですね。

2004/07/10 14:19:38
id:actual No.3

actual回答回数610ベストアンサー獲得回数12004/07/10 08:46:10

ポイント15pt

http://ja.wikipedia.org/wiki/%E5%9B%9B%E8%89%B2%E5%95%8F%E9%A1%8...

�����峨����� - Wikipedia

アルゴリズムの改良はなされているようですが・・・

http://www.geocities.co.jp/SiliconValley-Oakland/1680/puzzle/col...

M.Hiroi's Home Page / Puzzle De Programming

id:another

ありがとうございました。ですが、もう少し具体的な情報が欲しかったのでした。

2004/07/10 14:21:05

コメントはまだありません

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません