0

簡単な質問があります。2 つの決定問題がある場合、L1 と L2 とします。L1 が多項式時間で L2 に還元できる場合、L2 は多項式時間で L1 に還元できないというのは本当ですか?

私の理解では、これは次のことを意味します。

L1 can be reduced to L2 in polynomial time => NOT (L2 can be reduced to L1 in polynomial time)
=(L1 not in P) & (L2 in P) => (L1 in P) & (L2 not in P)
=[(L1 in P) OR (L2 not in P)] OR [(L1 in P) & L2 in P)]
=(L1 in P) OR (L2 not in P)

したがって、L1 を polytime で L2 に還元できるというステートメントは、L2 を polytime で L1 に還元できないことを意味します。これは、L1 が P にある場合、または L2 が P にない場合にのみ真です。そこにあるように、そうでない場合は、声明は誤りです。

私の論理は理にかなっていますか、それとも私は道を外れていますか? アドバイスや助けをいただければ幸いです。ありがとうございました！

4

1 に答える 1

1

「L 1 poly-time が L 2に還元される場合、L 2は L 1に還元されない」という一般的なステートメントは、一般に誤りです。P の任意の 2 つの問題 (∅ と Σ* を除く) は、相互にポリ時間還元可能です。多項式時間で問題を解き、必要に応じて yes または no の答えを出力するだけです。

2 つの問題間の多項式時間の削減可能性は、言語が P にあるかどうかについて何も保証しないため、特定のロジックは正しくありません。たとえば、停止問題は多項式時間で TM が特定の文字列を受け入れるかどうかの問題に還元できますが、どちらの問題も決定可能ではないため、どちらの問題も P にはありません。

お役に立てれば！

于 2013-11-01T03:28:43.990 に答える