超越数と計算複雑さの関係?

関係については、Hartmanis-Stearnsの推測がありますが、リアルタイム出力のTuring
Machine以外には、それ以上の推測や定理はありません。明らかに非合理的な代数はリアルタイムTMで出力することはできず、無限の超越数も存在する。しかし、リアルタイムTMとPのような同じ複雑さのクラスを超えて、不合理な代数と超越数はありますか?あるいは、超越数をさまざまな複雑さのクラスによって非理性的な代数から分離することができますか?

ベストアンサー

$ mathsf {E} = mathsf {DTIME}(2 ^
{O(n)})$よりも上の潜在的にすべての複雑さクラスをもたらす、これを見る別の方法は、バイナリ展開の実数を考慮することです。バイナリ展開が$
0 ^ infty $または$ 1 ^ infty
$で終わらない実数(つまり、ダイアディックの有理数ではない)は、一意のバイナリ展開を持ちます。このバイナリ展開を$ {0,1 }
^ { mathbb {N}} $の要素として扱うことができ、これは$ mathbb {N}
$の部分集合として見ることができます。 $ Sigma $の$ Sigma $を有限アルファベットの$ mathbb
{N} $の標準的な識別)を言語に変換します。次に、この言語の複雑さについて尋ねることができます。 (Dyadic
rationalsは、$ emptyset $や$ Sigma ^ *
$とはまったく異なる言語に対応しているので、とにかく面白いわけではありません…)

言語$ L $がその固有関数$ chi_L $をリアルタイム計算可能であるとすると、$ L $自体は$ mathsf
{E} $:与えられた入力$ x $の長さ$ n $にあり、 $ x $は長さ – 辞書順の$ N $番目の文字列です(つまり、 x
in Sigma ^ * $という文字列は、標準識別の下にある$ N in mathbb {N} $に対応します) 。
L $の$ x を決定するには、リアルタイムマシンを使用して$ chi_L $の最初の$ N $ビットを出力し、$ N
$番目のビットを読み出します。これは$ O(N)$時間かかる。しかし、$ | x | = log_ {| Sigma |} N
$であるので、これは$ O(| Sigma | ^ {| x |})= 2 ^ {O(| x |)} $ timeです。

(As far as I can tell the converse need not hold. Or at least,
the naive proof that I was thinking of doesn’t work. That is,
suppose $L in mathsf{E}$. The naive way decide the first $N$ bits
of $chi_L$ takes $approx N cdot 2^{O(log N)} = N^{1 + c}$ time
for $c > 0$.)

この識別を使用すると、原則として$ mathsf {E}
$に含まれていないすべての複雑なクラスを使用して、非リアルタイム計算可能な超越関数の「複雑さ」を理解しようとすることができます数字。
しかし、$ L $の複雑さの性質を$ chi_L
$が代数的であるか超越的であるかに関連付ける方法はわかりません。非常に興味深い質問として私を打ち明けます。
Emil
Jerabekがコメントで指摘しているように、この識別情報を使用すると、すべての代数はカウント階層$ mathsf {CH}
$の線形時間バージョンになります。 $ mathsf {E}
$にあります。したがって、このアプローチは、主に超越数の複雑さを区別するためではなく、互いに区別するために主に有用であると思われる。リアルタイムの計算可能な代数の複雑さ。

返信を残す

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