ログスペース削減に関してNC完全な問題はありますか?

問題はタイトルです。

私たちは皆、$ text {NL} $と$ text {P} $にこのような問題があることを知っています。ですから、$
text {NC} $についても同じことが考えられます。より興味深いことに、ログスペースの削減に関して、$ k
ge 2 $と任意の$ text {NC} ^ k $ -complete problemが存在しますか?
$
k = 1 $に対して、Barringtonの定理は、ログスペースの完全な問題。

$ text {NC} $にログスペースの問題があると、$ text {NC}
$階層が崩壊するようです。だから、タイトルの質問は開いているが、もう一つの質問はまだ立っている。

編集:元の(タイトル)質問がOPENであるように修正されました。これまでに残った質問が1つあります。

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

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