SATをサッと解く 〜乱択アルゴリズムで遊んだ話〜 - kivantium活動日記
ミレニアム問題と呼ばれる数学の7つの難問がある。各分野で重要かつ難しい問題が選ばれており、解決するとクレイ研究所から100万ドルの賞金を得ることができるということで有名だ。そのうちの1つポアンカレ予想は解決済みだが、残りの6つは未解決である。その中でもコンピュータ科学で非常に重要な問題が「P≠NP予想」である P≠NP予想とは コンピュータで問題を解決するときには一定の手続き（アルゴリズム）に従って問題を処理することになる。例えば数の集合の中からある特定の数字を見つけるという問題を考える。一番単純な解決方法は集合の要素を1つずつ調べていって値が求めたい数字になっているかどうかチェックすることだろう。この場合、集合がN個の数字からなるとすればおおよそNに比例する時間で求めたい数字の検索が終わることが予想できる。このようにだいたいNに比例する時間で終わるようなアルゴリズムについて、計算時間のオ
サルでも分かるビットコイン ～Bitcoinの仕組みを理解しよう～
はじめに 世界最大のBitcoin取引所（であった）Mt.Goxの破綻が大きなニュースになっていますが、ニュースを見る限りマスコミ側もBitcoinをよく理解しないまま報じているような印象を受けました。「採掘ができるらしい」「管理する中央機関がないから危ないらしい」などの断片的なことは知っていても、ビットコインが実際にどういった仕組みで動いているのかについて理解している人は少ないのではないでしょうか。そこで、以前私が調べて理解したことをまとめてみることにしました。（なおあくまで「私が理解したこと」なので、誤った情報が含まれているかもしれません。誤りに気がついた方はコメントしてください） Bitcoinに関する情報源 この文章を書くにあたって参考にしたページを挙げておきます。正確に理解したい方は原典に当たることをオススメします。 Nakamoto Satoshi Paper Bitcoinの
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
