アルゴリズム論 過去問01年
明日テストなので、過去問を解いてみる。ムズすぎる。
間違いだらけやと思うので、おかしいとこは教えてください。＞＜
1.言語{0^n1^m | n
制限なしのポスト対応問題のインスタンスに含まれる記号すべての前にa(決まった記号)をつけるという還元をつくる。
例えば、(110,11) というインスタンスは(a1a1a0,a1a1)と還元する。
これは、有限ステップなので停止し、解も保存してる。
(2)一個の記号だけのポスト
1の個数を数字と考えると、この問題のインスタンスはNP完全問題である分割問題のインスタンスである。
クラスNPに入ってるので可解。(分割問題がクラスNPに入ってることを示せばよい。。。?)
そんなことしなくても、pdaで簡単にシミュレートできちゃいますね◎
3.分割問題
(1)違いが5以内に分割
証明済みの分割問題のインスタンスをS={i1,i2,i3.....in}とし、これを還元する。
S'={i1,i2,i3.....in,1,1,1,1,1}
というインスタンスに還元する。これはO(n)ステップで可能。
S'はSを包含していて、
S'について2分割するのはSを総和の差が1,3,5で分割することに等しいので、
還元が見つかった。
差が2、4の時も別に示すため、
S''={i1,i2,i3.....in,2}
S'''={i1,i2,i3.....in,4}
という還元も作れば、5以内で分割がNP完全であることが示せたことになる。
(2)比が1:2になる分割
...わからん＞＜
最初に総和Sが3の倍数かどうかを判定するルーチンをつける、Sが3の倍数であれば、
S'={i1,i2.....in,S/3}
という還元を作ればよい。 これは、解の保存、決定性多項式時間で還元できるので示せた。
