問題タブ [computation-theory]

だから私は、URM Machineに非常に似ている抽象マシンのアセンブリ言語でプログラミングすることを学んでいます。URM マシンには 3 つの基本的な命令があります (一部の文献では 4 つ):
レジスタをゼロにするには: Z(r)
レジスタをインクリメントするには: S(r)
レジスタ r1 と r2 に同じ値が含まれている場合に行またはラベルにジャンプするには: J(r1,r2,l)
ここで、私の抽象マシンはさらに弱いです。なぜなら、ジャンプするために、レジスタとリテラル 0 の比較しかできないからです。
これを補うために、レジスタに任意の値を割り当てることができます (0 だけでなく、 URM) と基本的な算術演算。
どちらのマシンでも、無制限の数のレジスタを使用できます。

2 つの正の数を正常に比較して最大値を返すプログラムを作成できました。
ここで、プログラムが負の数も受け取れるようにしたいと思います。

私の質問: 数値が負かどうかを確認するにはどうすればよいですか? これらの命令だけでも可能ですか？

私は、この種の低レベル言語についてはあまり頭がよくないことを告白します...

私の最大のプログラムは次のとおりです：（入力はr1とr2で行われ、出力はr3で行われます）

ありがとうございました！

計算理論では、ProvableとDecidableという用語は交換可能ですか？それらは同じことを意味しますか？

たとえば、決定問題（Das Entscheidungsproblem）と呼ばれる何かが証明可能かどうかという質問をよく目にします。

TMが言語を認識し、受け入れ状態または拒否状態になった場合、言語は決定可能です。開発者として これは、プログラムにバッファオーバーフローまたはデッドロックが含まれているかどうかを判断できることを意味するため、重要だと思います。また、次の問題は決定不可能です。

• プログラムが初期化されていない変数にアクセスすることはありますか？
• 2つの文脈自由文法が同じ言語を記述していますか。
• サブルーチンへのパラメーターが参照またはコピー結果によって渡される場合、違いはありますか？

決定可能性の観点から、決定可能性の重要なポイントは何と言いますか。また、決定可能性が（特に開発者にとって）重要である理由は何ですか。

注：箇条書きは回答に問題はありません。トピックは自分で調べることができます。要点を知りたいだけです。

A が文脈自由でないことを示す必要があります。これには Pumping Lemma を使用する必要があると思いますが、どうすればよいでしょうか?

特定の文脈自由文法からすべての文字列を生成するアルゴリズムはありますか?

(n)(n+1)/2のi=1からnまでのΣ

与えられた n に対する計算の上限は? O(n^3)O(n^2)ですか？

例：

など、N の関数としてのこの計算の上限は? それは...ですか ：

O(n^3)?

コルモゴロフの複雑さがランダム性とランダムな入力にどのように関連しているかを誰かが説明してくれたら、私はとても感謝しています。

私が理解できないもう 1 つのことは、与えられた入力 X のコルモゴロフ複雑度を計算することは決定できないことです。それを考えると、どのようにしてランダム性の尺度になるのでしょうか?

ありがとう

チューリングマシンのシミュレーターコードを見ていると、次のステートメントに出くわしました

「テープは時間と位置をシンボルにマッピングします。シンボルを計算するには、1ステップ前にマシンを確認する必要があります。その時点で、ヘッドが要求された位置にあった場合、シンボルは表に従って、同じ位置にある前のシンボルとマシンがあった状態。それ以外の場合、シンボルは変更されませんでした。」

イタリック体の部分はどういう意味ですか？この文脈で要求された位置はどういう意味ですか？

私は大学でアルゴリズム分析と呼ばれるコースを持っており、現在、さまざまな複雑さのクラス (P、NP、NP 困難など) を研究しています。

NP と NP 困難の交差点としての NP 完全問題、および NP に含まれる P 問題については既に説明しました。主に NP 完全問題 (k-coloring、k-clique、SAT) のいくつかの例についても説明しました。

ほとんどの場合、問題が NP 完全であることは次の方法で証明されます。

を。それを解決するための非決定論的アルゴリズムを見つける (選択、成功、失敗を使用する)。

b. 既知の NP 完全問題をそれに還元します。

問題は、これらの問題が決定論的マシンで実行された場合 (選択肢に遭遇したときに同時に分岐するのではなく、順次)、指数時間の解決策があることです。

私の質問はこれです-多項式時間でも指数時間でも解決できない問題に遭遇したことはありません。多項式時間の問題は通常 P であり、指数時間の問題は通常 NP 完全です。

ここに役立つベン図があります: http://en.wikipedia.org/wiki/Np_complete

1. P でも NP-complete でも NP でもない問題の例を知りたいです。

2. また、セットの累乗セットを NP 完全に生成するような、本質的に指数関数的な問題はありますか? それとも、その名前は、それを解決するための明白な方法が他にないという理由だけで、指数時間アルゴリズムが使用される問題にのみ適用されますか?

わかりました。Rosh Oxymoronに答えを与えました。なぜなら、彼は実際に、P と NPC の間にあると疑われる問題の例をいくつか挙げていたからです。皆さんの助けに感謝します。実際、この質問を間違った場所に置いていることに気付きました。もあります： https://cstheory.stackexchange.com/

ここで、私の質問に対する次の非常に役立つ回答を見つけ ました : 最初の質問に正確に関連していない場合でも、これは一般的に興味深いものです。

どうもありがとう、

ダン

次の言語に問題があります。

文脈自由文法を書かなければなりません：

それを説明しています。私はすでにいくつかのエクササイズをしましたが、これは私にとって本当に難しいです。私は有用なアプローチなしで何時間も座っています。部分N0なしで文法を書くことは問題ではありません ：（m = l）v（l = 2n）。しかし、私はこれを成し遂げる方法がありません。アドバイスをいただければ幸いです。