The complexity of semilinear problems in succinct representation

Peter Burgisser, Felipe Cucker and Paulin Jacobe de Naurois
Issue Volume 15, Number 3 / October, 2006
Pages 197-235
http://dx.doi.org/10.1007/s00037-006-0213-6

d次元ユークリッド空間内の集合Sがsemilinearであるとは、それが半空間の論理結合で書けることである。
例えば、論理結合としてANDのみを使う場合は凸多面集合が得られる。
凸多面集合がいくつかの半空間のANDとして与えられて、また、空間中の点xが与えられたときに、
xがその凸多面集合に属しているかどうか判定する問題はよくある問題で線形計画問題と等価だけども、
チューリング機械を計算モデルとして採用するときには、これが多項式時間で解けるとわかっている (Khachiyan 1979)。
しかし、チューリング機械では実数を扱うことができない。
実数を扱うことができる計算モデルとしていわゆるBSSモデル (Blum-Shub-Smaleのモデル) があるけれども、
その上では非決定性多項式時間で解け、また補問題も非決定性多項式時間で解けるのに、
決定性多項式時間で解けるかどうかわかっていない (いわゆる、線形計画問題に対する強多項式時間アルゴリズムの存在性と関係がある)。

この論文ではこれら2つのモデルの中間に位置すると考えられる計算モデルを考える。
まず、考える半空間を線形不等式の係数は全て整数であるとする (定数項は実数であってもよい)。
そして、実数に対しては加算、減算、大小比較という3つの操作のみを許し、すなわち乗算や除算は許さない、という立場のモデルを考えるのである。
Tardos (1986) の結果は、このモデルにおいて線形計画問題が多項式時間で解けることを意味している。

この論文ではさらに、入力がadditive decision circuitという回路で与えられるとする。
そしてその場合に様々な問題がある意味で難しいということを証明している。
いままでにもそのような問題の例は知られていたが、ここでは23個もの問題の困難性を示していて興味深い。
特にトポロジーに関する問題が多く扱われている。