この有限グラフの問題は決定可能ですか？どの要因が問題を決定できますか？

Question

次の問題が決定できるかどうか、そしてどのように知るかを知りたいです。私が見るすべての問題は、「はい」または「いいえ」と言うことができます。 ここ)?

入力：$ v $および$ u $を頂点として、指示された有限グラフ$ g $
質問：初期頂点として$ u $を使用して$ g $のパスと最終頂点として$ v $が存在しますか？

Answer 1

有限量のデータのみを調べる必要がある問題は、すべての潜在的なソリューションを列挙することで構成されるアルゴリズムがあるため、決定可能です。それは途方もなく遅いかもしれませんが、それは関連性がありません。アルゴリズムがある場合、それは決定可能です。

あなたが述べている問題は有限のグラフを想定しており、それはそれが決定可能であることを強く示唆しています。厳密に言えば、もう少し調べる必要があります。問題は、グラフ内のパス上のプロパティであり、グラフにサイクルが含まれている場合、無限の数のパスがある場合があります（このサイクルの周りに何度もループできます）。ただし、問題を有限の問題に変えるのは簡単です。$ u $から始まり、サイクルを含む$ v $で終わるパスがある場合、そのパスのすべてのサイクルを切り取ることができます。サイクルを含まない新しいソリューション。サイクルが含まれない有限数のパスがあるため（グラフに$ k $エッジがある場合、ほとんど$ k！$パスが同じエッジを複数回使用しないパスがあります）。 $ u $から$ v $へのパスは清潔であるため、決定できます。

ちなみに、このプロパティは呼ばれます 接続性.

このアプローチは一般的なアプローチです 割引. 。簡単ではない問題を考えると、それを解決する方法を知っていた問題にそれを減らしました。

問題が判断できないことを証明することはしばしば困難です。問題が決定可能であることを証明するために、私たちがする必要があるのは、それを決定するアルゴリズムを示すことだけです。問題が判断不可能であることを証明するには、アルゴリズムが存在できないことを証明する必要があります。よく知られていない問題がいくつかあります。実際には、ほとんどの場合、問題が判断できないことを証明すると、問題を軽減する有名な有名な問題があることを示します。私たちの問題のアルゴリズムは、よく知られていない有名な問題を解決するので、私たちの問題も命中不可能でなければなりません。

「ほとんどの」問題が決定可能であるか、「ほとんどの」問題が決定できないと言うことはできません。いくつかの理論的な意味では、ほとんどすべての問題は有望ですが、「興味深い」問題に取り組む強い傾向があり、それらには解決策がある可能性が高くなります。

Answer 2

コメントでジルが指摘したように、問題は些細なことです。あなたの他の質問については...

いくつかを除いて、ほとんどの問題とアルゴリズムが決定可能です（提供されています ここ)?

いいえ。実際、 多くの 問題は判断できません。実際、多くの問題（言語）はありませんが、多くのチューリングマシンしか存在しません。つまり、ほとんどの場合、数え切れないほどの多くの決定可能な問題があります。

Answer 3

はい、これは決定可能です。なぜなら、すべての可能なパスを徹底的に検索できるからです。 「迂回」をスキップできるため、頂点を繰り返すパスを見る必要はありません。ただし、非反復パスの長さは、有限であるグラフのサイズに囲まれているため、そのようなパスが1つずつチェックできるようなパスは有限にあります。

決定できないのは次のとおりです。無限のグラフ$ g $と2つの頂点$ a $ a $と$ b $を考えると、$ a $から$ b $からパスがあるかどうかを決定します。グラフがOracleとして指定されている場合、これは決定できません。また、グラフがそれを計算するプログラムを介して指定されている場合、決定できません。

Answer 4

特定の問題が解除可能かどうかを示す方法はありません。時間が経つにつれて、特定の問題が解除できるかどうかにかかわらず、良い「予想」が得られるかもしれません。

私が通常することは次のとおりです。

1. 問題を解決してみてください。つまり、指定された問題を解決するコンピュータープログラムを考えてみてください。提案された問題については、非常に単純なプログラムは、可能なパスを確認するだけで、常にそれを見つけることができます（存在する場合）、またはそうでなければパスが存在しないことを教えてください。
2. 問題を明確に定式化します。多くの問題はあまりにも曖昧ですが、明らかに書かれている場合、決定可能かどうかを確認するのは非常に簡単です（他の問題と比較して、un/dicidableであることが知られている、または既知の方法を使用して ご飯の定理)
3. （2）が機能しなかったが、問題は把握できないと考えている場合、拘束されない問題（多くの場合、問題（またはその補数）が機能する）から減らすことでそれを証明してみてください。

ほとんどの場合、管理不可能な問題についてステップ（1）を実行しようとする場合、チェックするためにプログラムが必要になります 無限 ものの数。これは通常、問題が決定できないことの兆候です。