Complexity Zoo - Qwiki
Introduction Welcome to the Complexity Zoo... There are now 488 classes and counting! This information was originally moved from http://www.complexityzoo.com/ in August 2005, and is currently under the watchful eyes of its original creators: Zookeeper: Scott Aaronson Veterinarian: Greg Kuperberg Tour Guide: Christopher Granade Errors? Omissions? Misattributions? Your favorite class not here? The
複雑性クラス - Wikipedia
複雑性クラス一覧[編集] 以下の一覧の各複雑性クラスには補問題の集合である 'Co' の付くクラスが存在する。例えば、問題 L が NP に含まれるなら、その補問題は Co-NP に属する。 #P - NP問題の解を数える問題 #P完全 - #P の中で最も難しい問題群 AH - 算術的階層 AP - 交替性チューリングマシンで多項式時間で解ける問題のクラス BPP - 乱択アルゴリズムで多項式時間で解ける問題のクラス（解はおそらく正しい） BQP - 量子コンピュータで多項式時間で解ける問題のクラス（解はおそらく正しい） Co-NP - 非決定性機械で "NO" であることが多項式時間で決定可能な問題のクラス Co-NP完全 - Co-NP の中で最も難しい問題群 DSPACE(f(n)) - 決定性機械で空間計算量 O(f(n)) で解ける問題のクラス DTIME(f(n)) - 決定
巡回セールスマン問題 - Wikipedia
巡回セールスマン問題を総当たりで解く場合のイメージ。左側で一つずつ探していき、より効率のいいルートが見つかった場合、右側のグラフが更新される。 巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。 問題例の大きさは、都市の数で表される。この問題は、計算複雑性理論においてNP困難と呼ばれる問題のクラスに属する。すなわち、問題例の大きさに関する決定性の多項式時間アルゴリズムが見つかりそうにない、計算量的に困難な問題である。なお、この問題の特殊ケースとして考えられるハミル
原始再帰関数 - Wikipedia
原始再帰関数（げんしさいきかんすう、英: Primitive Recursive Function）とは、原始再帰と合成で定義される関数であり、再帰関数（計算可能関数）の部分集合である。原始帰納的関数とも。 再帰理論において原始再帰関数は、計算可能性の完全形式化のための重要な要素となる関数のクラスの1つである。このような関数は証明論においても重要である。 数論が扱う関数の多くや、実数を値とする関数の近似は原始再帰的であり、加法、除法、階乗、指数、n 番目の素数を求める関数などがある (Brainerd and Landweber, 1974年)。実際、原始再帰的でない関数を考案するのは難しいが、いくつかの例が知られている（限界の節を参照）。 計算複雑性理論では、原始再帰関数の集合をPRと呼ぶ。 原始再帰関数のクラスとは、while文を使用せずに計算できる（すなわちfor文のみで計算可能な）
Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak
Cambridge University Press This is a textbook on computational complexity theory. It is intended as a text for an advanced undergraduate course or introductory graduate course, or as a reference for researchers and students in computer science and allied fields such as mathematics and physics. See also Amazon page for the book. This page contains: Draft of the book with links to additional relevan
極限 - Wikipedia
極限値の性質[編集] 数列が収束するとき、その極限値はただ一つに限る。 収束する数列から項を有限個取り除いても、得られた数列は同じ値に収束する。 収束する数列は数の集合として有界である。 数列の発散[編集] 数列が収束しないとき、その数列は発散するという。特に、番号 n を限りなく大きくしていくとき、数列の項の値 an が限りなく大きくなることを、数列 {an} は正の無限大に発散するといい、 または のように表す。イプシロン-エヌ論法では、数列の正の無限大への発散は、 のように定式化される。 また、番号 n を限りなく大きくしていくとき、数列の項の値 an が限りなく小さくなることを、数列 {an} は負の無限大に発散するといい、 または、 と表す。数列 {an} が負の無限大へ発散することは、各項 an を反数にした数列 {bn} (bn = −an, n = 1, 2, 3, …)
単方向linked listの循環参照判定をO(n)で行なう - やねうらおブログ(移転しました)
「諸悪の根源は物理的」より。(id:ladybug:20051116経由) http://www.cotton-tree.com/garyu/archives/2005/11/post_156.html 単方向リンクリスト（連結リスト）がある。ノード数を n とするが、n の値は 分からない。リスト中にループ（循環参照）が存在するか否かを O(n) で判定する アルゴリズムを示せ。ただし、リストの各ノードの内容を変更してはならない。 つまり、単純にポインタが指したノード全てにマーキングをしておいて、 新しいノードに移るたびにマーキングされているかを調べることで判定することは 出来ない。 no markingが条件として与えられているが、当然、no labeling,no recursionで求めなければならない。labelingありなら、たとえば以下のように簡単に求まる。 bool isC
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
【ジャム】 JAM Project3 【プロジェクト】