Skip to main content
Link
Menu
Expand
(external link)
Document
Search
Copy
Copied
MathemaTCS
Home
記法
確率集中不等式
Markovの不等式
Chebyshevの不等式
Hoeffdingの不等式
Chernoffバウンド
リード-$k$族の和の集中不等式
情報理論
エントロピー
シャノンエントロピー
最小エントロピー
f-ダイバージェンス
KLダイバージェンス
χ²ダイバージェンス
統計距離
Pinskerの不等式
グラフ理論
エクスパンダーグラフ
ランダムグラフ
行列のスペクトル
ランダムネス
ランダムネス抽出器
サンプラー
ペア独立性
誤り訂正符号
復号化
符号の限界
Hadamard符号
Reed-Solomon符号
folded Reed-Solomon符号
連接符号
AEL距離増幅
Berlekamp-Welchアルゴリズム
ランダム線形符号
平均時計算量理論
問題の平均時困難性
関数の擬似ランダム性
ハードコア補題
Goldreich-Levinの定理
XOR補題
直積定理
埋め込みクリーク問題
Kučeraのアルゴリズム
AKSアルゴリズム
探索から判定への帰着
Learning with Error
BKWアルゴリズム
対話証明系
対話証明系の定義
ゼロ知識証明
NPに対するゼロ知識対話証明系
PCP定理
最悪時から平均時への帰着
行列積
パーマネント
正則化補題
高次元エクスパンダー
コラム
NP困難の定義と歴史
更新履歴
製作者: 清水 伸高
コラム一覧
数学の解説以外の雑多な内容のコラム記事をまとめています.
Table of contents
NP困難の定義と歴史