問題タブ [computation-theory]

コンパイルされたプログラムからサブルーチンを推論するためのアルゴリズム/テクニックを説明している論文はありますか? 言い換えれば、プログラムに複数回出現するコードのブロックを見つけるアルゴリズムはありますか? これらのブロックでは、一致を見つける可能性が高くなるように (もちろん、プログラムの動作を変更することなく) 命令を並べ替えることができます。

このプロセスは、呼び出しを回避するためにコンパイラーによって実行されるサブルーチンのインライン化の反対と見なすことができますが、バイナリ サイズは増加します。

これは非常に難しい理論的問題のように私には思えます。

だから、それは最終的な時間であり、私は古い試験でこの問題に出くわしました:

どこを示す正規表現を与えるdiff(x)：

例えば

私はしばらくこれに苦労していて、何も思い付くことができません。どんなポインタでも本当にありがたいです。

問題は、偶数の長さの単語のみを受け取るすべてのDFAの言語を前提として、それがPであるかどうかを証明することです。

開始状態から受け入れ状態までのすべてのパスを見つけるために、BFS /ダイクストラのアルゴリズムのようなもので特定のDFAを調べるチューリングマシンを作成することを検討しましたが、ループを処理する方法がわかりませんか？

ありがとう！

X^n の方が効率的だと思います。誰でも説明できますか？

ありがとう。

C ++テンプレート メタプログラミングはチューリング完全ですが、プリプロセッサ メタプログラミングは完全ではありません。

C++11 は、constexpr 関数の計算という新しい形式のメタプログラミングを提供します。この形式の計算はチューリング完全ですか? constexpr関数は再帰や条件演算子(?:)が許されているので、そうなのかなと思っているのですが、詳しい方に確認していただきたいです。

多くのものの削減は、対称的ではありません。私はそれを証明しようとしていますが、うまくいきません。

2つの言語AとBが与えられた場合、Aは次のように定義されます。

そしてB=A_TM、A_TMは決定不可能ですが、チューリング認識可能です！

次の削減が与えられた場合：

（ラテックスを使用していないことをお許しください。私はラテックスを使用した経験がありません）

ご覧のとおり、A <= B（AからA_TM）への削減が可能であり、うまく機能します。しかし、なぜB<=Aが不可能なのかわかりません。

明確にして説明してもらえますか？

ありがとうロン

私は複雑性理論を研究しており、確かなプログラミングのバックグラウンドを持っていますが、これほど多くのことが人間に固有の時間内に実行されるように見えるのはいつも奇妙に思えます。これがなぜなのか、誰かが何か考えを持っているのだろうか？

私は一般的に 1 秒から 1 時間の範囲の時間について話しています。コンピューターが処理できる 1 秒あたりの数十億の操作に比例して、その時間間隔がどれほど狭いかを考えると、これほど多くのことがそのカテゴリに分類されるのは奇妙に思えます。

いくつかの例:

ビデオのエンコード: 20 分

更新の確認: 5 秒

コンピュータの起動: 45 秒

あなたはアイデアを得る...

ほとんどのものは、瞬時か数百万年かのどちらかに分類されるべきだと思いませんか?

したがって、anxnゲームボードがあり、ボード上の各場所には整数があります。プレーヤー1は行1から番号を選択し、プレーヤー2は行2から番号を選択し、行がなくなるまで交互に表示します。次に、それらはすべての数字を合計し、合計が所定の合計Sに等しい場合はプレーヤー1が勝ち、そうでない場合はプレーヤー2が勝ちます。特定のボードと合計（B、S）に対するプレーヤー1の勝利戦略は、プレーヤー2が何をしてもプレーヤー1が勝つことができるかどうかです。この問題がPSpaceで完全であることを示したい

したがって、最初に、それがPSpaceにあることを示す必要があります。これは、移動の総数がボードのサイズ（n ^ 2）によって制限されるため、非常に簡単だと思います。

PSpaceが難しいことを示すのに行き詰まっていますが、QSATから削減する必要があることはわかっていますが、その方法がわかりません。誰かが助けることができますか？

編集：実際、私はQSATから削減する必要があることを知りませんが、周りを検索した後、QSATが最も可能性の高い候補であるように見えます。他の多くの2人用ゲーム（地理が最も顕著な例です）はQSATから減少しているので、これも必要だと思いました。ただし、これについて間違っている場合は、遠慮なく訂正してください。

この言語が規則的かどうかを証明するにはどうすればよいですか?

L = {a ⁿ b ⁿ : n≥1} 和集合 {a ⁿ b ⁿ⁺² : n≥1}