この回のタイトルは茫洋としていて、12回の中でもっとも中身が分からないだろうタイトルでした。 （第1～3回の内容から、あの話題かな、と分かる人はいたかもしれませんが。）
第3回で、超平面配置の組合せ的構造を有向マトロイドで表すことができる、ということを紹介したのですが、 実は、有向マトロイドのクラスは超平面配置に対応するものよりは少し広くなっていて、 超平面配置の各超平面を歪めたもの（擬超平面配置）に対応することになります。 この擬超平面配置のクラスが有向マトロイドのクラスと一致するという「トポロジー的表現定理」は このあたりのトピックの中で重要かつ有名です。
この回の話題は、2次元の場合、すなわち、平面上の擬直線配置が与えられたとき、 それと組合せ的な構造が同じ直線配置にすることができるかどうか？ という話です。 これは、言い替えると、ランク3の有向マトロイドが与えられたときに、それが直線配置のクラスに入るかどうか、という ことです。
ここで、擬直線配置というのは、直線の代わりに曲線を複数平面上に配置することですが、 条件としては、各曲線は自己交差しないこと、そして、2つの曲線はちょうど1点で交わる、ということになります。 （2つ目の方の条件について、平面では平行な2直線を許していたのですが、これは(片方の)無限遠で交わると解釈する形になります。）
まず、平面の場合でも、直線配置と組合せ的に異なる擬直線配置がある、ということが、下の有名な配置から分かります。 下図の左側は黒い直線が8本書かれていますが、この配置に対して「パップスの定理」という射影幾何学における定理があって、 図の3点D,E,Fは図に赤い点線で示しているように必ず1直線に並びます。
擬直線配置としては、ここに右図のように1つの曲線を、DとFは通るけれどEは通らないように加えることができてしまいます。 しかし、この状況を保ったまますべての線を直線で描こうとすると、パップスの定理に反してしまい、実現不可能ということになります。 このことから、擬超平面配置の中には、2次元からすでに、通常の超平面配置としては実現できないものが混ざってくるということが 分かります。
そうすると、それでは与えられた擬直線配置が直線配置で実現できるのかどうかをどうやって判別できるか？ ということになります。 これは、擬直線配置の伸張可能性問題（Strechability）と呼ばれる問題です。
この回は、この判定問題がNP-困難である、ということの証明を紹介しました。 紹介したのは、Peter Shorの1991年の論文の証明方法で、うまい擬直線配置を構成することにより、 3SATという典型的なNP-完全問題を多項式時間帰着できることを示します。
この問題はその後にMnëvの普遍性定理というものが与えられ、Existential theory of the reals (ETR)という問題と 多項式時間等価であることが示されていて、こちらの結果の方が強い主張なので、 この問題に関してはこちらが紹介されることが多いと思います。 この記事でShorの証明を紹介したのは、1つは分かりやすく面白い証明だったからということ。 もう1つは、第4回ではNP-完全/困難性を証明する方法として典型的な、別のNP-完全問題への帰着という手法を見せる例として ちょうどよいと思ったから、でした。
ある問題がNP-完全/困難であることを示すための典型的な方法は、別のすでにNP-完全/困難であることが知られている問題を その問題へ多項式時間帰着できることを示す、という方法です。第4回でNPの紹介を書いた際に、この例も入れたいところだったの ですが、とてもページ数に余裕がなく、その部分を今回にずらし込む、というのが今回の記事の役割なのでした。
実は、当初の計画では、NP完全/困難性の証明の例も（何か適当なよく知られた問題を具体例として）第4回の方に入れ、 この伸張可能性問題も第4回の最後に少し触れて、というようなことを考えていました。 その第4回の原稿締切がGW明け、というタイミングでGW前半に確認のためにShorの論文を読んでいたところ、 この証明の仕組みが面白く、次の1回分で解説すると分かりやすいかな、と思い、方針転換したのでした。 （そのときにすでに第4回のページ数には多項式時間帰着の例を入れられないという状況だった、というのもその理由の1つでした。）
(Shorは量子計算での素因数分解アルゴリズムで有名な方で、それ以前にはこんな研究成果も出していたのでした。)
八森正泰