È $ Nhalt $ indecididabile anche se $ m $ ferma in ingresso $ W $ in passi finiti

Question

Se abbiamo la lingua

$ Nhalt={; $ $ m $ halts onInput $ w $ in meno di $ n $ passaggi \} $

è anche questa lingua anche indecidabile nello stesso modo in cui $ halt $ è undecidabile?E se sì, $ Nhalt \ Notin P $ , giusto?

Answer 1

Questa lingua è ovviamente decidabile, appena emula $ m $ su $ W $ e vedere se si trattafermato entro $ N $ passaggi o no ...

Ora, a sensolo $ Nhalt \ in P $ o $ Nhalt \ Notin P $ .La lunghezza della classe $ N $ qui è logaritmico al suo "valore" (supponendo che $ \ Sigma $ quinon è un anno).Pertanto, il numero di passi che avremo bisogno di emulare sarebbe esponenziale nelle sue dimensioni!Non vedo un algoritmo di tempo polinomiale per quello, quindi I Supponiamo che probabilmente non è in P .Ma non ho dimostrato che (ha appena dato l'intuizione sul perché potrebbe essere il caso), e c'è anche una possibilità che mostra che è equivalente ad un problema aperto (forse in qualche modo potresti provare la sua $ \ Mathcal {NP-Complete} $ ?)