# A reduction from $HP$ to $\{(\langle M \rangle, \langle k \rangle) : \text{M visits in at list$k$states for any input}\}$ I tried to define the next reduction from $$HP$$ to $$\{(\langle M \rangle, \langle k \rangle) : \text{M visits in at list k states for any input}\}$$.

Given a couple $$(\langle M\rangle , \langle x\rangle)$$ we define $$M_x$$ such that for any input $$y$$, $$M_x$$ simulates $$M$$ on the input $$x$$. We denote $$Q_M +c$$ the number of states needed for the simulation of $$M$$ on $$x$$, and define more special states for $$M_x$$ $$q_1′,q_2′,…,q_{Q_M + c+ 1}’$$ when $$q’_{Q_M +c+1}$$ is defined as the only final state of $$M_x$$. Now, in case $$M_x$$ simulation of $$M$$ on $$x$$ halts (i.e $$M$$ reach one of its finite state) $$M_x$$ move to $$q_1’$$ and then continue to walk through all the special states till it reaches $$q_{Q_M + c + 1}$$.

We define the reduction $$(\langle M \rangle , \langle x \rangle) \longrightarrow (\langle M_x \rangle , \langle Q_M +c+1 \rangle)$$

In case $$((\langle M \rangle , \langle x \rangle) \in HP$$ then for any input $$y$$ , $$M_x$$ walks through all the special states and thus visits in at least $$Q_m + c+ 1$$ steps. Otherwise, $$M$$ doesn’t stop on $$x$$ so $$M_x$$ doesn’t visit any special state, thus visits at most $$Q_M +c$$ states (the states needed for the simulation).

It is ok? If you have other ideas or suggestions please let me know. Posted on Categories proxies