326752 ランダム
 ホーム | 日記 | プロフィール 【フォローする】 【ログイン】

謎犬の耳

謎犬の耳

【毎日開催】
15記事にいいね!で1ポイント
10秒滞在
いいね! --/--
おめでとうございます!
ミッションを達成しました。
※「ポイントを獲得する」ボタンを押すと広告が表示されます。
x

PR

キーワードサーチ

▼キーワード検索

プロフィール

謎様

謎様

カレンダー

ニューストピックス

お気に入りブログ

まだ登録されていません

コメント新着

王島将春@ Re:頭の中は最強の実験室(10/29) はじめまして。福井市在住の王島将春(お…
言葉の量化と数の言葉の量化@ 自然数は、言葉である ≪…妖怪の集団…≫の≪…至高のアフォーダンス……
式神自然数@ 時間軸の数直線 十進法の基での桁表示の西洋数学の成果の…
絵本のまち有田川@ Re:数学でつまずくのはなぜか(08/20) 自然数は、[絵本][もろはのつるぎ]で…
気まぐれ@ Re:「エクセルギー」のすすめ(10/19) 最後の 「この著者は「定圧下でなくても」…

カテゴリ

フリーページ

2005年09月30日
XML
カテゴリ:科学本
「量子コンピュータとは何か」ジョージ・ジョンソン(水谷 淳訳)(早川書房)

そろそろ佳境です。この本の最終章「宇宙一の難問」について。

P203 セールスマン巡回問題は「NP完全」すなわち「非決定論的に多項式時間で」解ける。つまり非決定論的コンピュータというものがあって、そいつは問題を解く各ステップでどの筋道を選ぶかランダムに決めるのだけれど、100%幸運な万能機械であり、その偶然に選んだ筋道が常に正しい選択肢になっている。この場合は「多項式時間」で解けるわけだ。しかし普通のコンピュータ(量子コンピュータも)は決定論的なのでこの問題の解決には「指数関数的時間」がかかる。

P206 「充足化問題」も「NP完全」。出席者全員を満足させるパーティーの組み方はやはり人数に対して指数関数的に難しさが増大する。

P208 「NP=P」を証明できるか?もしそれができれば、「ある定理を証明するのは(証明が存在するとして)、それをチェックするのと同じくらい簡単なことになる」。フェルマーの最終定理は解くのに350年もかかったが、それが正しいかどうかチェックするのには数ヶ月しかかからなかった。NP=Pならば芸術作品の「創作は鑑定と同じくらい簡単なものになる」という比喩も面白い(新たなモーツァルトを生み出すこと)。






お気に入りの記事を「いいね!」で応援しよう

最終更新日  2005年09月30日 17時47分51秒
コメント(0) | コメントを書く
[科学本] カテゴリの最新記事


バックナンバー

・2024年06月
・2024年05月
2024年04月
2024年03月
・2024年02月

© Rakuten Group, Inc.