線形時間帰着
着目している問題がNP完全問題であることを証明するために用いられる手法は多項式時間帰着と言われるが、線形時間帰着に条件を絞っても当てはまることが多い。
より狭い条件が当てはまるのなら、そっちの用語を使いたくなる。
しかし、文章のロジックに含意を含むためちょっと読みづらいかもしれない。
問題 $ P はNP完全問題 $ Q に線形時間帰着できる。線形時間帰着は多項式時間帰着でもある。よって問題$ PはNP完全問題 $ Q に多項式時間帰着できるということでもある。従って、問題$ PはNP完全問題である。
これを略して、「問題 $ P はNP完全問題 $ Q に線形時間帰着できるため問題$ PはNP完全問題である」と書いているが文章のロジックに含意を含むため読みづらいかもしれない。