証明方法E_tm = {M | Mは何も受け入れないチューリングマシンです}はNP-Hardですか？

Question

私は始める方法もわかりません。 私の考えは、いくつかのNP完全な問題から多時間短縮を提供することです。 E_tm

私が理解できないことは、E_tmは決定できないが、NP-Hardクラスは決定可能であることを知っていることです。

Answer 1

ソリューション：

DF：問題もthoughitはNP自体（P326 Sipser）にではないかもしれないが、NPのすべての問題は、それに還元多項式時間であれば、NP困難である（唯一の定義は、私たちの本は持っています） 。 多項式時間をEtmに減らすことができることを示すならば、NPにある任意の言語L 'に対して。 これはEtmがNP困難であることを証明します。 L 'はNPによって定義されているので、L'を決めるようなTM（NTMがありますが、それらはパワーIでTMと同等です）M 'が存在します。

TM M'' that takes as an input <M,w> constructs 
TM M' such that 
on arbitrary x 
if w = x 
    run M on w if accept => reject 
        if reject => accept 
else reject. 

したがって、Mはすべての入力を拒否する場合はwを受け入れます。 それを確認しましょう。まず、Mがwを受け入れた後、任意の入力に対してM "を棄却し、したがってL（M"）=空であると仮定する。 Mがwを拒否し、M "が受け入れられ、したがってL（M"）が空でないと仮定します。 M ''を構成するには多項式時間がかかることに注意してください。 これで証明が完了しました。