11

私は本Computational Complexity: A Modern Approachを読んでいますが、忘却のチューリングマシンを理解するのに問題があります。

忘却のチューリング マシン (TM) は、そのヘッドの動きが入力の長さによって完全に決定されるような TM です。つまり、TM はその入力を認識しません。ここまでは順調ですね。

しかし、演習の 1 つは、次の定理を証明することです。

If a language L is decidable in time T(n) 
then there exists an oblivious TM that decides L in time O(T(n)^2).

L忘却の TM が の元の入力ではなく、何らかのコード化されたバージョンで動作する必要があることは明らかです。つまり、定理の要点は、ビット列を整数(忘却 TM の入力の長さ) にコーディングすることです。しかし、(ビット文字列) の可能な入力のセットを整数にコーディングしたい場合、長さ のビット文字列があるため、非常に大きな数にすぐに遭遇します。L2^nn

問題を正しく理解していますか? 定理をどのように証明しますか?

4

1 に答える 1

7

ここで、この論文を読むことをお勧めします。要求されたより低い時間境界で証明を与えてくれる、かなり興味深く素晴らしい論文です。(あなたはそれを O(N^2) に仕上げることができるはずだと思います。または、O(N*log(N)) は技術的には O(N^2) であると結論付けることができると思いますが、この証明に直接従うと、教授を怒らせる可能性があります。彼はあなたに別の方法でアプローチすることを意図していると思います。

編集：

論文への元のリンクは機能しなくなりました。ここに別の公開投稿があります。

http://www-dev.ccs.neu.edu/home/viola/classes/papers/PippengerF-Oblivious.pdf

Michael J. Fischer と Nicholas Pippenger による「Relations Among Complexity Measures」、1979 年。

于 2013-03-08T23:01:44.077 に答える