NP complete problem. NP完全な問題のこと. SAT (論理式充足問題) や 3Color (地図を3色で塗り分けられるかどうか) など多くの問題がこの問題である.
リスト::数学関連
久しぶりに更新します。 最近『Computers and Intractability』という、NP完全問題に関する本を読んでいました。 www.amazon.co.jp いくつか分からない単語とかがあり、それらを一応？解決したので覚書として記録します。多項式階層以下が分からなかった感じですが、復習としてクラスPやNP、NP完全についても触れておきます。 クラスP クラスNP NP完全 多項式階層 NP-easy 疑似多項式時間アルゴリズム 強力なNP完全性 クラスP 決定性Turing機械で、多項式時間で解ける(yesかnoかの判別がつく)問題のクラス。 計算量の関数yが、入力xに関して、y…
◆メモ 量子コンピュータの仕組みを、専門外の人間にもわかるように解説した本。原理から、その応用、発展が期待できる分野までを紹介する。 ハードウェアの実現には、本書の時点ではまだ時間がかかるとされている。しかし2010年代には、NSAやIBM、中国などが初歩的なプロセッサの開発に成功しているようだ。 はじめに 量子コンピュータの原理は、原子をスイッチとして扱い数を扱うというものである。 原子は、従来のスイッチと異なり、0と1だけでなくその0と1の両方を持った状態をとれる。これは量子の性質によるもので、従来のスイッチと比較にならない量のデータを扱うことができる。 現在の暗号は、「大きな数の因数分解…
AIや難しいアルゴリズムに憧れる人は少なくないと思いますが、そのような高度は技術が常に最適解であるとは限りません。高度ではない技術には、以下のようなメリットがあります。・人間が結果を予想しやすい・保守が容易である 一言で言うと、「扱いやすい」ということがメリットになります。高度ではない技術は、人海戦術になりがちで導入コストがかかり、システム構築時のヒューマンエラーも起こりがちですが、システムを保守・運用する上では、そのようなデメリットよりも「扱いやすい」というメリットが上回る場合が少なくありません。 この記事では、高度ではない技術の方が優れていたという例を２つ挙げます。 １．ソースコードの変数…
はじめに 2022-01-08、オープンソースのnpmパッケージであるcolors.jsとfaker.jsの作者が、不具合を引き起こす実装を意図的に含めたこれらの最新バージョンを公開した。 それらを利用しているプロジェクトは影響を被り、問題のコードが含まれないバージョンへのダウングレードによって当座の問題を回避したはずだ。 その後、colors.jsは2022-01-11時点で問題を含むバージョン(1.4.1や1.4.2など)はnpmからunpublishされたため、npmの最新は安全なバージョン(1.4.0)へと変更済みだ。ゆえにunpublishまでの数日間において^1.0.0のようにキャ…
ja.wikipedia.org
gitanez.seesaa.net
www.gizmodo.jp
www.net.c.dendai.ac.jp
edu.net.c.dendai.ac.jp
