Language in $R \setminus \mathit{NP}$ I am wondering whether the language $$L_{\textrm{hanoi}} = \{\langle k,s \rangle \mid \text{$s$ is a solution of Tower of Hanoi problem on $k$ rings}\}$$ is in $R\setminus \mathit{NP}$.
I want to claim that there is a Turing machine that solves the problem, therefore, $L_{\mathrm{hanoi}} \in R$, but given a solution to the problem, verifying that it is a valid solution takes $\Omega (2^k)$. However, $2^k$ could be be linear to the length of the input (number and sequence).
Is my solution valid? If not, how can I construct a language in $R \setminus \mathit{NP}$?
We always measure the running time of a machine with respect to input size. For this reason, your language is in P. Given a sequence of moves, you can easily check in polynomial time that the sequence is valid.
You can construct a language in $R \setminus \mathit{NP}$ using diagonalization. This is the content of the nondeterministic time hierarchy theorem.