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

$\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$ に対し、$A{\le }_{p}B$ は $A$ が $B$ に多項式時間多対一帰着（カープ帰着）可能であること、すなわち多項式時間で計算できる全域関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ で、すべての $x\in {\Sigma }^{\ast }$ について $x\in A⟺f(x)\in B$ となるものが存在することを表す。$\mathrm{NP}$ 完全性はこの ${\le }_p$ に関するものとする。$\mathrm{L}$, $\mathrm{P}$, $\mathrm{NP}$, $\mathrm{PSPACE}$, $\mathrm{NPSPACE}$ は標準的な計算量クラスとする。

次の主張のうち、（未解決問題の答えによらず）正しいと証明されているものをすべて選べ。

• ア　すべての言語 $A,B$ について、$A{\le }_{p}B$ かつ $B\in \mathrm{P}$ ならば $A\in \mathrm{P}$ である。
• イ　すべての言語 $A,B$ について、$A{\le }_{p}B$ かつ $A\in \mathrm{P}$ ならば $B\in \mathrm{P}$ である。
• ウ　すべての言語 $A,B$ について、$A$ が $\mathrm{NP}$ 完全で、$B\in \mathrm{NP}$ かつ $A{\le }_{p}B$ ならば、$B$ は $\mathrm{NP}$ 完全である。
• エ　$\mathrm{L}=\mathrm{PSPACE}$ である。
• オ　$\mathrm{NPSPACE}=\mathrm{PSPACE}$ である。
• カ　すべての言語 $A,B$ について、$A{\le }_{p}B$ ならば $B{\le }_{p}A$ である。

$\Sigma =\{0,1\}$ とし、言語とは ${\Sigma }^{\ast }$ の部分集合のこととする。チューリング機械 $M$ と入力 $w\in {\Sigma }^{\ast }$ の組の符号化を $⟨M,w⟩\in {\Sigma }^{\ast }$ と書き、停止問題を
$$\mathrm{HALT}=\{⟨M,w⟩\mid M\text{ は入力 }w\text{ に対して停止する}\}$$
と定める（正しい符号化になっていない列は $\mathrm{HALT}$ に属さないものとする）。$\overline{\mathrm{HALT}}={\Sigma }^{\ast }\setminus \mathrm{HALT}$ とする。

言語 $A,B$ について、$A{\le }_{m}B$ とは、計算可能な全域関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ で、すべての $x\in {\Sigma }^{\ast }$ について $x\in A⟺f(x)\in B$ となるものが存在することとする。また、言語 $L$ が帰納的可算であるとは、$L$ のちょうどすべての元に対して停止して受理するチューリング機械（$L$ に属さない入力に対しては受理しない）が存在することとする。

次のア〜カのうち、正しいものをすべて選べ。

ア　$\mathrm{HALT}$ は帰納的可算である。

イ　$\overline{\mathrm{HALT}}$ は帰納的可算である。

ウ　$\mathrm{HALT}$ は決定可能である。

エ　任意の決定可能な言語 $A$ について $A{\le }_m\mathrm{HALT}$ が成り立つ。

オ　ある決定可能な言語 $A$ について $\mathrm{HALT}{\le }_{m}A$ が成り立つ。

カ　$\overline{\mathrm{HALT}}{\le }_m\mathrm{HALT}$ が成り立つ。

アルファベットを $\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 完全である。