空間と時間の階層は匹敵しますか?

宇宙と時間の階層がどの問題がより難しいのか「意見の不一致」がどの程度あるかについての結果があるかどうかは疑問です。たとえば、$
L_1 in DeclareMathOperator {TIME} {TIME} TIME(f(n)) setminus
SPACE(g(n))、L_2などの言語$ L_1 $および$ L_2 $が存在するかどうかは、 in
DeclareMathOperator {SPACE} SPACE(g(n)) setminus
TIME(f(n))$?これはどのくらいの頻度で発生しますか?

PS-質問はスペースに依存する計算時間を伴う関数が質問するようです似たようなものですが、紛らわしい言葉を言い、答えのどれも私が探しているものではありません。

ベストアンサー

あなたは、奇妙な関数$ f(n)$と$ g(n)$を選択することで、記述した状況を得ることができます。

For example, let $g(n) = n^3$ and $$f(n) = begin{cases} n &
text{if $n$ is odd}, \ 2^{n^5} & text{if $n$ is even}.
end{cases} $$

次のように$ L_1 $と$ L_2 $を選択します:

$ L_1 $は時間が$ O(2 ^ {n ^ 5})$であるが、時間$ O(2 ^ {n ^
4})$では決まらない偶数長の文字列のみを含む言語です。そのような言語の存在は、時間階層の定理から証明するのはかなり簡単です。

$ L_2 $は、空間$ O(n ^ 3)$では決めることができるが、空間$ O(n ^
2)$では決定できない奇数長の文字列のみを含む言語です。このような言語の存在は、空間階層定理から証明するのはかなり簡単です。

次に、私たちは次の事実を持っています:

$ L_1 TIME(f(n))$:

文字列が$ L_1 $にあるかどうかを判断するには、長さ$ n $が偶数であるかどうかを確認するだけです。そうであれば、$
L_1 $の定義によって存在が保​​証されている$ L_1 $に対して$ O(2 ^ {n ^ 5})$時間判定子を使用し続ける。 $
n $が奇数の場合、$ L_1 $には奇数の文字列が含まれていないので、直ちに拒否します。この手続きは、$ L_1 $を決定し、$ n
$が奇数のときは$ O(n)$で実行され、$ n $が偶数のときは$ O(2 ^ {n ^
5})$で実行されます。換言すれば、この手順は、時間$ O(f(n))$における$ L_1
$を決定する。必要に応じて、TIME(f(n))$の$ L_1 。

SPACEの$ L_2 (g(n))$:

$ L_2 $の定義により、$ L_2 $は空間$ O(n ^ 3)$で決めることができます。したがって、SPACE(n ^
3)= SPACE(g(n))$の$ L_2 は必要に応じて$です。

$ L_1 not SPACE(g(n))$:

SPACE(g(n))= SPACE(n ^ 3)$の$ L_1 が矛盾しているとします。私たちは$ SPACE(n ^
3) subseteq TIME(2 ^ {O(n ^ 3)} subsetneq TIME(2 ^ {n ^
4})$を知っています。したがって、時間$ O(2 ^ {n ^ 4})$で動作する$ L_1 $の決定子が存在します。これは$
L_1 $の定義と直接矛盾します。次に、矛盾によって、$ L_1 not
がSPACE(g(n))$にあることがわかります。

$ L_2 not TIME(f(n))$:

TIME(f(n))$の$ L_2 という矛盾を考えてみましょう。これは、定数$ c $と、$ L_2
$を決定するアルゴリズム$ A $が存在することを意味します。これは、サイズ$ n $の任意の入力に対して、アルゴリズム$ A
$は時間$ c times f(n)$で終了します。

新しいアルゴリズム$ A
‘$を次のように構築する。ある入力を与えて、入力全体を辿り、入力の長さが偶数か奇数かを追跡する。入力の終わりに長さが奇数と判断された場合は、入力の先頭に戻り、$
A $を実行します。それ以外の場合は拒否します奇数長の入力に対して、$ A ‘$は$ A $と同じ答えを返します。 $ L_2
$には偶数長の文字列が含まれていないため、偶数長の入力に対しては、$ A ‘$は拒否されます。したがって、$ A ‘$も$ L_2
$を決定します。偶数長の入力では、正確に$ n $ステップで$ A ‘$が実行されます。奇数長の入力では、$ A ‘$は$ A
$以上のステップで正確に$ 2n $ステップ実行されます。しかし、$ A $は多くの$ c times f(n)$
stepsを必要とし、奇数$ n $は$ cn $です。従って、すべての場合において、$ A ‘$は多くとも$(c + 2)n
$ステップで実行される。つまり、アルゴリズム$ A ‘$は時間$ O(n)$で$ L_2 $を決定します。

しかし、$ TIME(n) subseteq SPACE(n)$以来、SPACE(n) subsetneq SPACE(n
^ 2)$の$ L_2 と結論づけることができます。これは$ L_2
$の定義と矛盾します。したがって、矛盾によって、TIME(f(n))$の$ L_2 not が表示されます。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です