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

$\Sigma =\{0,1\}$ とし、言語とは ${\Sigma }^{\ast }$ の部分集合のこととする。言語 $L$ の補集合を $\overline{L}={\Sigma }^{\ast }\setminus L$ と書く。言語 $X,Y$ について、$X{\le }_{p}Y$ とは、多項式時間で計算できる全域関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ で、すべての $x\in {\Sigma }^{\ast }$ について $x\in X⟺f(x)\in Y$ となるものが存在することとする。

いま、言語 $A,B$ について $A\in \mathrm{P}$、$B\in \mathrm{NP}$ であることだけがわかっている。次のア〜オの言語のうち、それぞれに書かれた条件だけから「$\mathrm{NP}$ に属する」と必ず結論できるものをすべて選べ。

ア　ある言語 $H$ について $C{\le }_{p}H$ かつ $H{\le }_{p}A$ をみたす言語 $C$

イ　$D{\le }_{p}B$ をみたす言語 $D$

ウ　$A{\le }_{p}E$ をみたす言語 $E$

エ　$\overline{F}{\le }_{p}A$ をみたす言語 $F$

オ　$B{\le }_{p}G$ をみたす言語 $G$

$\Sigma =\{0,1\}$ とし、言語とは ${\Sigma }^{\ast }$（空列 $\epsilon$ を含む $\Sigma$ 上の有限列全体）の部分集合のこととする。言語 $A,B$ について、$A{\le }_{p}B$ とは、多項式時間で計算できる全域関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ であって、すべての $x\in {\Sigma }^{\ast }$ に対して $x\in A⟺f(x)\in B$ を満たすものが存在することとする。クラス $\mathcal{C}$ に対して、言語 $A$ が $\mathcal{C}$ 困難であるとは、すべての $L\in \mathcal{C}$ について $L{\le }_{p}A$ が成り立つことをいう。$A$ が $\mathcal{C}$ 困難であり、かつ $A\in \mathcal{C}$ であるとき、$A$ は $\mathcal{C}$ 完全であるという。計算モデルは多テープの決定性・非決定性チューリング機械とし、$\mathrm{P},\mathrm{NP},\mathrm{EXP}={\bigcup }_{k\ge 1}\mathrm{DTIME}(2^{n^k}),\mathrm{NL},\mathrm{PSPACE},\mathrm{NPSPACE}$ は通常の意味の計算量クラスとする。また、停止問題を $\mathrm{HALT}=\{⟨M,w⟩:\text{決定性チューリング機械 }M\text{ は入力 }w\text{ で停止する}\}$ とする。ここで $⟨\cdot ,\cdot ⟩$ は機械と入力の組の標準的な符号化（符号化と記述の相互変換が多項式時間でできるもの）であり、正しい符号化になっていない列は $\mathrm{HALT}$ に属さないものとする。

次のア〜カのうち、（未解決問題の仮定なしに）正しいと証明されている主張をすべて選べ。

ア. $\varnothing$ でも ${\Sigma }^{\ast }$ でもない任意の言語 $A\in \mathrm{P}$ は $\mathrm{P}$ 完全である。

イ. 空集合 $\varnothing$ は $\mathrm{NP}$ 困難である。

ウ. $\mathrm{HALT}$ は $\mathrm{NP}$ 困難である。

エ. $\mathrm{PSPACE}⊊\mathrm{NPSPACE}$ である。

オ. $\mathrm{EXP}$ 完全な言語であって $\mathrm{P}$ に属するものが存在する。

カ. $\mathrm{NL}⊊\mathrm{PSPACE}$ である。

$\Sigma =\{0,1\}$ とし、言語とは ${\Sigma }^{\ast }$（空列を含む $\Sigma$ 上の有限列全体）の部分集合のこととする。言語 $A$ の補集合を $\overline{A}={\Sigma }^{\ast }\setminus A$ と書く。言語 $A,B$ に対し、多項式時間で計算できる全域関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ であって、すべての $x\in {\Sigma }^{\ast }$ について
$$x\in A⟺f(x)\in B$$
をみたすものが存在するとき、$A{\le }_{p}B$（多項式時間多対一帰着可能）と書く。$\mathrm{P}$ は決定性チューリング機械で多項式時間で判定できる言語のクラス、$\mathrm{EXP}$ はある $k$ について時間 $2^{O(n^k)}$ で判定できる言語のクラスとする。

次のア〜カのうち、正しい（証明できる）ものをすべて選べ。ただし、ア〜オでは $A,B,C$ は任意の言語とする。

ア. $A{\le }_{p}B$ かつ $B\in \mathrm{P}$ ならば $A\in \mathrm{P}$ である。

イ. $A{\le }_{p}B$ かつ $A\in \mathrm{P}$ ならば $B\in \mathrm{P}$ である。

ウ. $A{\le }_{p}B$ かつ $B{\le }_{p}C$ ならば $A{\le }_{p}C$ である。

エ. $A{\le }_{p}B$ ならば $\overline{A}{\le }_p\overline{B}$ である。

オ. $A\in \mathrm{P}$ ならば、任意の言語 $B$ について $A{\le }_{p}B$ である。

カ. $\mathrm{P}⊊\mathrm{EXP}$ である。

アルファベットを $\Sigma =\{0,1\}$ とし、言語とは ${\Sigma }^{\ast }$ の部分集合のこととする。言語 $A,B$ について、多項式時間で計算できる関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ で、すべての $x\in {\Sigma }^{\ast }$ に対して $x\in A⟺f(x)\in B$ をみたすものが存在するとき $A{\le }_{p}B$ と書く（多項式時間多対一帰着）。NP 完全性はこの ${\le }_p$ に関するものとする。また、$\mathrm{SAT}$ は CNF 論理式の充足可能性問題、$\mathrm{HALT}=\{⟨M,x⟩\mid \text{チューリング機械 }M\text{ は入力 }x\text{ で停止する}\}$ は停止問題（$\Sigma$ 上の適当な符号化によるもの）とする。

次のア〜カのうち、（未解決問題の仮定を一切用いずに）正しいと証明されている命題をすべて選べ。

ア. $A{\le }_{p}B$ かつ $B\in \mathrm{NP}$ ならば $A\in \mathrm{NP}$ である。

イ. $A{\le }_{p}B$ かつ $A\in \mathrm{P}$ ならば $B\in \mathrm{P}$ である。

ウ. $\mathrm{P}⊊\mathrm{EXP}$ である。

エ. $\mathrm{HALT}{\le }_p\mathrm{SAT}$ である。

オ. ある NP 完全な言語 $L$ が $\mathrm{coNP}$ に属するならば、$\mathrm{NP}=\mathrm{coNP}$ である。

カ. $A\in \mathrm{P}$ であり、$B$ が $B\ne \varnothing$ かつ $B\ne {\Sigma }^{\ast }$ をみたす任意の言語（決定可能でなくてもよい）ならば、$A{\le }_{p}B$ である。

言語はすべてアルファベット $\Sigma =\{0,1\}$ 上の言語（${\Sigma }^{\ast }$ の部分集合）とする。言語 $A,B$ に対し、$A{\le }_{p}B$ は多項式時間多対一帰着（カープ帰着）が存在すること、すなわち多項式時間で計算できる関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ で、すべての $x\in {\Sigma }^{\ast }$ について $x\in A⟺f(x)\in B$ となるものが存在することを表す。NP 完全性はこの ${\le }_p$ に関して定める（$\mathrm{NP}$ に属し、$\mathrm{NP}$ のすべての言語が ${\le }_p$ で帰着されること）。また $\mathrm{EXP}={\bigcup }_{k\ge 1}\mathrm{DTIME}(2^{n^k})$、$\mathrm{NL}$ は非決定性対数領域で判定できる言語のクラス、$\mathrm{PSPACE}$ は決定性多項式領域で判定できる言語のクラスとし、$\mathrm{HALT}$ はチューリング機械の停止問題（決定不能である）を表す言語とする。

次のア〜キのうち、正しい（現在知られている結果から真であることが証明されている）ものをすべて選べ。

ア. 任意の言語 $A,B$ について、$A{\le }_{p}B$ かつ $B\in \mathrm{P}$ ならば $A\in \mathrm{P}$ である。

イ. 任意の言語 $A,B$ について、$A{\le }_{p}B$ かつ $A\in \mathrm{NP}$ ならば $B\in \mathrm{NP}$ である。

ウ. 任意の言語 $B,C$ について、$B$ が NP 完全で、$B{\le }_{p}C$ かつ $C\in \mathrm{NP}$ ならば、$C$ は NP 完全である。

エ. $\mathrm{P}⊊\mathrm{EXP}$ である。

オ. 任意の言語 $A,B$ について、$A{\le }_{p}B$ ならば $B{\le }_{p}A$ である。

カ. $\mathrm{NL}⊊\mathrm{PSPACE}$ である。

キ. $\mathrm{P}$ に属するすべての言語は NP 完全である。