computer-science - poly-time 関数クラスは再帰的に列挙可能ですか?

Question

Poly-time 関数を定義すると、最大多項式 (n) 時間 (n は入力のサイズ) でチューリング マシンによって計算できる関数です。これらの関数のクラスは再帰的に列挙可能ですか?

Answer 1

答えはイエスです。実際、私は本の中に証拠を見つけました。すべてのおかげで、与えられた指示で私を大いに助けました:)

Answer 2

答えはノーだと確信しています。Poly-time 関数を再帰的に列挙するプログラムは、巡回セールスマン問題を解決する関数が Poly-time であるかどうかをある時点で通知する必要があります。その特定の質問に答えられるかどうかは、現時点ではまだ未解決です。

そのひどい答えで何を吸っていたのかわかりません。巡回セールスマンの問題が Poly-time でない場合、プログラムはその事実を発見する必要はありません。それに対する解決策をリストアップすることは絶対に避けなければなりません。決して見つからないので、これは簡単です。

私がはっきりしていない重要な詳細の 1 つは、関数をどのように表現しているか、および一意の関数と見なすものです。

function が「Poly-time で実行されるプログラム」に等しく、同じ出力を生成するかどうかに関係なく、すべてのプログラムをリストしたいとします。すると、答えは「与えられたプログラムが Poly-time の場合、その事実の証拠は常にありますか？」それは明らかに誤りです。未解決の問題の証明のためにポリ時間を検索するプログラムを作成できます。それが見つかった場合、最終出力を生成する前に指数関数的な時間を無駄にします。このプログラムはポリ時間ですが、未解決問題が偽であることを証明しないと証明できません。

関数が「入力を出力に関連付ける規則」に等しく、同じ関数をエンコードする複数のプログラムをリストすることに問題があるとします。その証拠が発見された場合に時間を無駄にするのではなく、以前の病理学的関数を変更してその出力を変更しましょう。これで、このプログラムが poly time であることを証明できますが、証明ステップ全体を実行しない (そしておそらくその出力を変更する) 関数とは異なる関数を表しているかどうかを証明することはできません。

関数が「入力を出力に関連付ける規則」に等しく、同じ関数をエンコードするがすべてを必要としない複数のプログラムをリストしても問題ないとします。これprogは、ポリ時間である場合もそうでない場合もp(x)あり、多項式であるプログラムであるとします。p(x)最初の forステップをエミュレートする 2 番目のプログラムを作成するのは簡単です。この 2 番目のプログラムは、ポリ時間であることが保証されています。実際にprogが poly 時間である場合、この形式のプログラムは同じ関数を表すprogため、出力のリストにはすべての可能な poly 関数が含まれます。(ただし、同じ関数がさまざまな方法でエンコードされます。)