アルゴリズム・計算量分野の成果として,多くの問題が本質的に解くことが難しいこと
が示されており,最近では公開鍵暗号系や認証システムなどでその難しさを利用した
情報システムも開発されている.一方で,本質的に解くのが難しいからこそ,実際に現れる
そのような難しい問題をなんとか現実的時間内でよい精度で解くことが要求される.
そのようなアルゴリズム,特に難しい問題をなんとか解く近似アルゴリズムの開発の世界
では,最近種々の新しいアルゴリズム設計パラダイムの登場があった.本稿では,
そのような近似アルゴリズム設計手法の代表的なものとして,線形計画法の主相対アプローチを近似アルゴリズム設計に拡張したもの,線形計画(と半定値計画)とランダム化
を組み合わせたものの2つについて,集合と論理にかんする疑問を例題に解説する.