計算理論・ラムダ計算の問題

難易度 2大学院の講義の演習問題レベル証明問題大学院数学計算理論・ラムダ計算

$n$ を正の整数とし、変数 $x_{1}, \dots, x_{n}$ のブール回路を次のように定める。大きさ $s$ （ $s \geq 1$ ）の回路とは、ゲートの列 $g_{1}, g_{2}, \dots, g_{s}$ であって、各ゲート $g_{i}$ が
- 種類 $AND$ , $OR$ , $NOT$ のいずれか 1 つと、
- 入力として、 $AND$ , $OR$ のときは $x_{1}, \dots, x_{n}, g_{1}, \dots, g_{i - 1}$ の中から選んだ順序付きの 2 つ組 $(u_{i}, v_{i})$ （ $u_{i} = v_{i}$ も許す）、 $NOT$ のときは同じ候補の中から選んだ 1 つの $u_{i}$

をもつものとする。入力 $a \in {0, 1}^{n}$ に対し、 $x_{j}$ の値を $a_{j}$ とし、 $g_{1}, g_{2}, \dots$ の順に、 $g_{i}$ の値を $u_{i}, v_{i}$ の値の論理積・論理和、または $u_{i}$ の値の否定として定める。回路が計算する関数とは、 $a$ に最後のゲート $g_{s}$ の値を対応させる関数 ${0, 1}^{n} \to {0, 1}$ のことである。

関数 $f : {0, 1}^{n} \to {0, 1}$ が変数 $x_{j}$ に依存するとは、第 $j$ 成分だけが異なる $a, a^{'} \in {0, 1}^{n}$ で $f (a) \neq = f (a^{'})$ となるものが存在することをいう。

$f$ がすべての変数 $x_{1}, \dots, x_{n}$ に依存するとき、 $f$ を計算するどの回路においても、種類が $AND$ または $OR$ であるゲートの個数は $n - 1$ 以上であることを証明せよ。

この問題で使うもの

小さな回路で計算できる関数（説明と入口の問題）

この問題を解けるようになるまで（31 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

出力 $g_{s}$ に影響しうるゲートと変数を頂点とし、「ゲートとその使われる入力」を辺で結んだグラフを考える。連結グラフの辺の本数は頂点数 $- 1$ 以上であることを使う。

ヒント 2

出力から入力の向きに遡って届くゲートの集合 $H$ を作る。 $f$ がすべての変数に依存することから、どの変数も $H$ のどれかのゲートの入力として現れることを、値が変わらないことの帰納法で示す。

ヒント 3

$H$ の $AND$ ・ $OR$ ゲートを $b$ 個、 $NOT$ ゲートを $c$ 個とすると、辺は $2 b + c$ 本、頂点は $b + c + n$ 個になる。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

出力から入力を遡って届くゲートの集合（出力に影響しうる部分回路）を定め、その各ゲートから出力への道があることを述べている（2 点）
$f$ がすべての変数に依存することから、各変数がこの部分回路のいずれかのゲートの入力として現れることを、入力の 1 成分を変えても各ゲートの値が変わらないという帰納法で示している（3 点）
ゲートと入力を結ぶグラフが連結であり、辺の本数が頂点数 $- 1$ 以上であることを、理由を付けて使っている（2 点）
辺の本数 $2 b + c$ と頂点数 $b + c + n$ を数えて $b \geq n - 1$ を導き、回路全体の $AND$ ・ $OR$ ゲートが $n - 1$ 個以上と結論している（3 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

方針: 出力 $g_{s}$ に影響しうるゲートと変数を頂点とするグラフを考え、それが連結であることと、すべての変数が頂点に含まれることから、辺の本数を評価する。

$f$ はすべての変数に依存するとし、 $C = (g_{1}, \dots, g_{s})$ を $f$ を計算する回路とする。ゲート $g_{i}$ の使われる入力とは、 $AND$ , $OR$ のときは $u_{i}, v_{i}$ 、 $NOT$ のときは $u_{i}$ のこととする。

頂点集合の定義. ゲートの集合 $H$ を「 $g_{s}$ を含み、 $H$ に属するゲートの使われる入力のうちゲートであるものも $H$ に属する」ような最小の集合とする。具体的には、 $i = s, s - 1, \dots, 1$ の順に、 $g_{i} = g_{s}$ であるか、または $g_{i}$ がすでに $H$ に入れたゲートの使われる入力であるときに $g_{i}$ を $H$ に入れる（使われる入力は添字の小さいゲートなので、この順で決められる）。この作り方から、 $H$ の各ゲートからは「使われる入力 $\to$ そのゲート」の向きに辿って $g_{s}$ に至る道がある。さらに、 $H$ のゲートの使われる入力として現れる変数全体を $X_{H}$ とし、 $V = H \cup X_{H}$ とおく。

補題 1. $X_{H} = {x_{1}, \dots, x_{n}}$ 。

証明. ある $j$ について $x_{j} \in / X_{H}$ と仮定して矛盾を導く。 $a, a^{'}$ を第 $j$ 成分だけが異なる入力とする。 $H$ のゲート $g_{i}$ について、 $a$ での値と $a^{'}$ での値が等しいことを、 $i$ に関する（ $H$ に属する添字についての）強い帰納法で示す。 $g_{i} \in H$ の使われる入力は、変数ならば $X_{H}$ に属するので $x_{j}$ ではなく、 $a$ と $a^{'}$ で値が等しい。ゲートならば $H$ に属し添字が $i$ より小さいので、帰納法の仮定により値が等しい。 $g_{i}$ の値は使われる入力の値だけで決まるので、 $g_{i}$ の値も等しい。特に $g_{s} \in H$ について $f (a) = f (a^{'})$ 。これがすべての $a, a^{'}$ で成り立つので $f$ は $x_{j}$ に依存せず、仮定に反する。 $□$

グラフ. 頂点集合を $V$ とし、 $H$ の各ゲート $g_{i}$ とその使われる入力 $w$ の組ごとに辺 ${g_{i}, w}$ を 1 本引いた無向の多重グラフ $G$ を考える（ $u_{i} = v_{i}$ のときは同じ 2 頂点を結ぶ辺が 2 本になる）。使われる入力は、ゲートなら $H$ に、変数なら $X_{H}$ に属するので、辺の両端は $V$ に属する。

補題 2. $G$ は連結である。

証明. $H$ の各ゲートからは、 $G$ の辺を辿って $g_{s}$ に至る道がある（ $H$ の作り方による）。 $X_{H}$ の変数 $x$ は、ある $g_{i} \in H$ の使われる入力なので辺 ${g_{i}, x}$ で $g_{i}$ とつながり、そこから $g_{s}$ に至る。よってすべての頂点が $g_{s}$ と同じ連結成分に属する。 $□$

辺の本数の評価. $H$ に属する $AND$ , $OR$ ゲートの個数を $b$ 、 $NOT$ ゲートの個数を $c$ とする。辺は $AND$ , $OR$ ゲートから 2 本ずつ、 $NOT$ ゲートから 1 本ずつ出るので、辺の本数は $2 b + c$ である。頂点数は、補題 1 より $∣ V ∣ = ∣ H ∣ + ∣ X_{H} ∣ = b + c + n$ 。連結な多重グラフでは、辺の本数は頂点数から 1 を引いた数以上である（辺を 1 本ずつ加えるごとに連結成分の個数は高々 1 しか減らず、はじめ $∣ V ∣$ 個の成分が 1 個になるには $∣ V ∣ - 1$ 本以上の辺が要る）。補題 2 よりこれを $G$ に使えて、
$2 b + c \geq (b + c + n) - 1, すなわち b \geq n - 1.$

結論. 回路 $C$ 全体の $AND$ , $OR$ ゲートの個数は、 $H$ に属するものの個数 $b$ 以上なので $n - 1$ 以上である。

以上より、すべての変数に依存する関数 $f$ を計算するどの回路も、 $AND$ または $OR$ のゲートを $n - 1$ 個以上含む。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる