L/poly
計算の複雑さの理論では、L / polyは、多項式の量のアドバイスを持つ対数宇宙機の複雑さのクラスです。L / polyは、不均一な対数空間クラスであり、不均一な多項式時間クラスP/polyに類似しています。
形式的には、形式言語 LがL / polyに属するためには、整数nをnの長さ多項式の文字列にマップするアドバイス関数fと、2つの読み取り専用入力テープと1つの読み取りを備えたチューリングマシンMが存在する必要が -マシンMが入力x、 f（n）を受け入れる場合に限り、長さnの入力xがLに属するように、サイズが対数のテープを入力サイズに書き込みます。あるいは、もっと簡単に言えば、Lは、によって認識できる場合に限り、L/polyになります。多項式サイズの分岐プログラム。これら2つの計算モデルのパワーが同等であることを証明する一方向は、多項式サイズの分岐プログラムが存在する場合、アドバイス関数で指定し、チューリングマシンでシミュレーションできるという観察結果です。他の方向では、対数書き込み可能スペースと多項式アドバイステープを備えたチューリングマシンは、書き込み可能テープの構成と他の2つのチューリングマシンヘッドの位置の組み合わせを表す状態を表す分岐プログラムによってシミュレートできます。テープ。
1979年に、Aleliunas等。対称ログスペースがL/polyに含まれていることを示しました。ただし、この結果は、SLが均一なログスペースに折りたたまれるというOmerReingoldの結果に取って代わられました。
BPLは、エーデルマンの定理の変形であるL/polyに含まれています。
参考文献
^ 複雑さの動物園： L/poly。
^ Thierauf、Thomas（2000）、同等性と同形性の問題の計算の複雑さ、コンピュータサイエンスの講義ノート、vol。1852年、Springer-Verlag、p。66、ISBN 978-3-540-41032-4。
^ Cobham、Alan（1966）、「完全な正方形のセットの認識問題」、スイッチングとオートマトン理論に関する第7回IEEEシンポジウムの議事録（SWAT 1966）、78〜87頁、doi：10.1109 / SWAT.1966.30 。
^ Aleliunas、Romas; カープ、リチャードM .; リプトン、リチャードJ .; Lovász、László ; Rackoff、Charles（1979）、「ランダムウォーク、ユニバーサルトラバーサルシーケンス、および迷路問題の複雑さ」、コンピュータサイエンスの基礎に関する第20回年次シンポジウムの議事録、ニューヨーク：IEEE、pp。218–223、doi：10.1109 / SFCS .1979.34、MR 0598110 。
^ Reingold、Omer（2008）、「ログスペースでの無向接続」、Journal of the ACM、55（4）：1–24、doi：10.1145 / 1391289.1391291、MR 2445014 。
^ Nisan、Noam（1993）、「ログスペースのランダム性への1回限りのアクセスと複数のアクセスについて」、Theoretical Computer Science、107（1）：135–144、doi：10.1016 / 0304-3975（93）90258-U、MR 1201169 。
P≟NP
この理論計算機科学関連