私見

問1､問2ともに成り立つ

A=(X_A,Y_A)の任意のインスタンスに対するB(X_B,Y_B)のインスタンスが存在している
Aのアルゴリズムを,検証アルゴリズムをとする
- - $x∈X$
  - $f_A(x)=1,x∈Y$
  - $f_A(x)=0,x∈X \setminus Y$
  - $f'_A(y\sharp c)=1,y∈X \setminus Y$
同様にBのアルゴリズムを $f_b$ ,検証アルゴリズムを $f'_B(y_B\sharp c_B)$ とする
- $f_b$ の定義はほぼAと同一なので略｡
BはNPであるが､AがNPであるかどうかは示されていない｡
- Aの(多項式)検証アルゴリズム､及びcertificate cは存在しているか不明｡

Bの検証アルゴリズムとBのcertificateはそのままAの検証に利用できる

多項式変換の定義 (組み合わせ最適p424)

定義15.17 P_1 = (X_1,Y_1)とP_2=(X_2,Y_2)を決定問題とする全てのx_1 ∈ Y_1に対して f(x_1) ∈Y_2であり､かつ全てのx_1 ∈ X1\Y2に対してf(x_1) ∈ X_2 \Y_2となる多項式時間計算可能な関数f:X_1→X_2が存在する時､P_1はP_2に多項式変換(polynomially transform)されるという｡

より $A \leq_P B$ の多項式変換可能な時､Aの任意のインスタンをBの任意のインスタンスに変換する多項式時間アルゴリズムfが存在する｡そのfを今回は $f_t$ とする(transのtとした)

この時Aに対する検証アルゴリズムは $f'_b(f_t(y_A)\sharp c)$ と表すことができる｡この関数の計算量はPでありかつAの任意のイエスインスタンスをBのcertificateを使って検証可能｡

問2のco-NPも同様
補問題の定義 $\overline{A} =(X_A,X_A-Y_A)$
- $\overline{A}$ の問題空間はAと同じ｡
- $\overline{A}$ のyes-instanceはAのno-instanceとなる
- のno-instanceに対するcertificate(を示す)を行える証明bit cは上記NPに関する証明と同じ手段で存在することは示せる｡
  - - 表記の都合上no-instanceをnとした
故にこのco-NPなBに多項式帰着可能な問題Aは何らかの問題の補問題になっているといえる｡
なんかおかしいこと書いてたら教えてください
関係ないけど数式内(tex)に使う#が不格好｡
- なんかこの記号多分Markdownとtexのメタ文字とかぶってるからうまくエスケープできない