アルゴリズム論　過去問04年

アルゴリズム 証明

1.1テープと2テープのTMの性能差

  • 言語{0^n1^n}

2テープ：O(n)
1テープ：O(nlogn)

  • 言語{xcxR}

2テープ：O(n)
1テープ：O(n^2)


教科書にあったの。
説明は直感的でいいみたいなので、交差列の説明とかはいらんかな？？？


2.空集合問題の非可解性
教科書どおりの還元。


3.頂点被覆
グラフG=(V,E)があったときに、すべての道(枝)を見張るのに、頂点に警備員を何人配置すればいいかって考えればわかりやすい。

(1)頂点数6でサイズ３の頂点被覆、サイズ２の頂点被覆は存在しない例

シンプルいずべすと。ベンゼンみたい。


(2)頂点被覆と独立集合の関係
頂点被覆のインスタンス(G,s)が真の時、独立集合のインスタンス(G,(V-s))も真になる。
Vはここでは、頂点数のことを表す。
V-sが0の時は例外として、(G,1)が真が成り立つ。


(3)最大独立集合のNP完全性証明
頂点被覆のインスタンス（G,s)から独立集合のインスタンスへの還元を考える。
(2)で還元のyes,noを調べた。　この変換は多項式時間決定性TMでできるので、還元が示せた。