<<アルゴリズム入門>>の第3版を読んでいます。定理 34.2 (ページ 1059) の証明があります。
多項式時間アルゴリズムによって決定される言語のクラスは、多項式時間アルゴリズムによって受け入れられる言語のクラスのサブセットであるため、 L が多項式時間アルゴリズムによって受け入れられる場合、多項式時間によって決定されることを示すだけで済みます。アルゴリズム。ある多項式時間アルゴリズム Aが受け入れる言語を L とします...(証明は省略します)...したがって、A はLを決定する多項式時間アルゴリズムです。
これは、A と B の 2 つの集合があり、A が B の部分集合であり、元 x∈A である場合、これは x∈B を証明するという意味だと思います。
また、「多項式時間アルゴリズムによって決定される言語のクラスは、多項式時間アルゴリズムによって受け入れられる言語のクラスのサブセットである」ことを理解しています。だから、この証明は私を混乱させます...