この対称圧縮性の概念とKolmogorovの複雑さとの関係は何ですか?

$ x $のビットを保持する文字列$ x $と置換$ g $がある場合、$ g $の値を格納する代わりに$ g $と$ g
$をそれぞれ格納することができます$ x $であり、この情報を使って明らかな方法で$ x $を再構築することができます。

$ M_x $を任意の入力を与えられたテープに$ x $を出力するチューリングマシンとし、$
enc(M)$をチューリングマシンの合理的なエンコーディングとし、生成されたサブグループを$ langle g rangle
$とする$ g $。 {0,1 } ^ n $で与えられた$ x

$ K(x)= min_ {M_x in M_x} | enc(M)| $、

S_n mid for n [ n、x_i = x_ {i ^ g} } $の$ Aut(x)= {g

$ orb(g)= | {i ^ { lang g} mid { in [n] } | $、

$ i番目の軌道$ g $の$ x $の$ b_ {g、i}($)$での$ g
に対して、軌道を既に発注して注文する最も低い要素に存在する。

$ enc(g)$は、任意の入力に対してサイクル記法で$ g $を出力するチューリングマシンの最小符号化であるように、S_n
$で$ enc $から$ g まで拡張します。

最後に、$ GC(x)= min_ {g in Aut(G)} |を定義する。 b_ {g、1} … b_
{g、orb(g)} enc(g)| $。

私は$ K $と$ GC $の関係について興味があります。特に、$ i $の関数として$ K(x_i)
in(GC(x_i))$が存在するような文字列$ x_ {i in mathbb {N}}
$のファミリーが存在することが疑われます。純粋なチューリングマシンよりもパーミュテーションがはるかに賢明ではないように見えるという事実以外に、それを証明する方法や本当に私がそれを疑う理由を知りません。他の自然なことは、どういうわけか、これらの2つのことがほぼ同じことを測定していることであり、何らかの形で、この対称方法は、Kolmogorovの種類の圧縮に対して「完全」であるということです。

ベストアンサー

それらは同等です。任意の$ x $に対して$ g_x $は、$ {i in i [n]:x_i = 0 }
$(例えば昇順)と$ {i in [n]:x_i = 1 } $(昇順でも)。 “GC”の記述はちょうど$
01enc(g)$で、その長さは$ 2 + K(g)$です。しかし、$ g_x $の上記の記述は$ x $から$ g_x
$の一様な構成を与えるので、$ K(g) leq K(x)+ O(1)$です。したがって、$ GC(x) leq 2 +
K(g) leq K(x)+ O(1)$があります。

返信を残す

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