多項式時間削減

Question

$ l_1 $および$ l_2 $は、アルファベット$ sum $で定義されている2つの言語です。 $ l_1 $は、多項式時間で$ l_2 $に削減できます。次のうちどれが真実ではないのですか？

• $ l_1 in p $ and $ l_2 $は有限です
• $ l_1 in np $および$ l_2 in p $
• $ l_1 $は決定できず、$ l_2 $は決定可能です
• $ l_1 $は再帰的に列挙可能であり、$ l_2 $は再帰的です

私の推論は次のとおりです、

$ a le_p b $、および$ b in p $の場合、$ a $は多項式時間で$ b $に減らすことができ、多項式時間で解決できます。したがって、私は最初、2番目の選択を偽り、したがって正しい答えだと考えました。

ただし、マッピングの削減に関する同じ引数を使用すると、3番目の選択も誤っているようです。 4番目の選択は、3番目の選択肢と同じです。

私は最初の選択について何でも推論することに失敗しました。

上記の議論を文脈に置くために、私は計算の理論について学んでおり、計算可能性と複雑さの理論の表面をざっと読んでいます。ヘロミーアウト。

Answer 1

3つのオプションは同じトリックを使用します。$ c1、c2 $が2つのクラスの言語と$ c1 subseteq c2 $です。 C2 $の$ l1 は、$ l1 notin c1 $を意味するものではありません。

真実にできない唯一の選択肢は3です。決定不可能な言語$ l_1 $から決定可能な言語$ l_2 $への多項式時間の短縮がある場合、$ l_1 $も削除可能になります（削減を計算するチューリングマシンを構築するだけですそして、$ l_2 $）の決定者を使用して問題を解決します。これは矛盾です。