Higher Order Unconstrained Binary Optimizationの計算困難性

Higher Order unconstrained Binary Optimization(HOBO)の計算困難性を考えてみました。結論として、HOBOはFP^NP完全問題です。

FP^NPは、SAT問題(論理式の充足可能性を判定する問題)を解くオラクルに問い合わせできる計算機で多項式時間で解ける関数問題の集合です。ここで、「SAT問題を解くオラクル」とはSAT問題を渡すとその答えを即座に返してくれる計算機で、「関数問題」とは答えが数値の問題を意味します。

この記事ではその結論の証明を概説したいと思います。

この記事の元ネタは、先日勉強会で受けた質問です。勉強会でQuadratic Unconstrained Binary Optimization(QUBO)の計算困難性を紹介したのですが、その時HOBOの計算困難性について質問が来ました。(後に少し説明しますが、)HOBOはQUBOの一般化となっています。

HOBOとは

HOBOは変数が0または1をとる多項式の最小値を求める問題です。式で書きますと、以下の値を求める問題です。

$$
\min_{x_1, \dots, x_n} \sum_{S\subseteq \{1, \ldots, n\}} Q_S \prod_{i\in S} x_i 
$$

ここで、変数$${x_1, \ldots, x_n}$$は0または1をとる変数で、係数$${Q_S}$$は整数とします。したがって、$${\sum_{S\subseteq \{1, \ldots, n\}} Q_S \prod_{i\in S} x_i}$$は値が整数の多項式となります。

HOBOはQUBOの一般化です。なぜなら、QUBOは変数が0か1をとる2次式の最小値を求める問題ですので、HOBOはQUBOを含むからです。

QUBOは、量子コンピュータ(アニーリング型)で解くことができる問題です。ちなみに、QUBOもFP^NP完全問題なので、HOBOとQUBOは同程度の難しさということになります。そしてこのことはHOBOも、QUBOと同様に、2QBFが解けないということを導きます。

QUBOの計算複雑性と2QBFに関しては過去記事を御覧ください。

HOBOの解き方

少し話が脱線しました。HOBOはFP^NPに含まれることを示すために、HOBOがSAT問題(論理式の充足可能性を判定する問題)を解くオラクルに問い合わせできる計算機で多項式時間で解けることを解説します。

(天下り的ですが、)HOBOは以下の流れで解くことができます。下記不等式が成り立つ変数$${x_1,\dots,x_n}$$の付値が存在するかを、右辺のqを変えつつ何度か判定します。付値が存在するqの中で最小のものがHOBOの解となります。

$$
\sum_{S\subseteq \{1, \ldots, n\}} Q_S \prod_{i\in S} x_i\le q 
$$

そして、この不等式が成り立つかの判定はSAT問題に変換できるので、SAT問題を解くオラクルで解くことができます。(どのようにして不等式判定問題をSAT問題に変化するかを粗く説明します。上記多項式を表す論理回路を作りそれを論理式で表します。そして多項式の値がq以下であるという条件を論理式に追加します。全部の論理式を満たす入力があるかの判定はSAT問題となり、入力がある場合かつそのときだけ不等式を満たす変数$${x_1,\dots,x_n}$$が存在します。)

不等式の判定回数はHOBOのサイズの多項式程度です。以下に説明します。HOBOの解は$${q\in[\sum\{Q_S\mid Q_S\le 0\}, 0]}$$の範囲にある整数なので、二分探索を用いてqを選び不等式判定を行えば、多くてもだいたい上記範囲の対数分($${\log_2 |\sum\{Q_S\mid Q_S\le 0\}|}$$)の回数で解は求まります。この範囲の対数は、HOBOのサイズ、すなわちHOBOの式(を表現したものの)の大きさの多項式程度となっています。

以上をまとめますと、HOBOはSAT問題を多項式回解くことで解が求まります。よって、HOBOがSAT問題を解くオラクルに問い合わせできる計算機で多項式時間で解けることがわかり、定義よりHOBOがFP^NPに含まれることがわかります。

HOBOがFP^NP完全であることを示すにはHOBOがFP^NPに含まれること以外に、FP^NPの問題全てがHOBOに変換できることを示す必要があります。これはFP^NP完全問題である01線形整数計画法がHOBOに変換できることを示すことで、証明できます。01線形整数計画法は変数が0か1をとる線形計画法です。

雑談

FP^NP問題はNPを解くオラクルを何度も問い合わせしたら解ける問題なので、FP^NP問題はNPよりも難しい問題と考えられます。NP問題でも解くのに大変時間のかかる難しい問題と言われているのに、それよりも難しいということです。

ちなみに、linear unconstrained binary optimization(HOBOの多項式を線形式にした最小値を求める問題)は多項式時間で解けます。具体的な解き方は、各変数についた係数の正負を確認し、負ならその変数を1に正ならその変数を0にし、すべての変数への付値がわかったら線形式の値を計算するだけです。すごく簡単に解けます。線形式だと簡単に解けるのに、2次式になると(かなり)難しくなる。不思議ですね。