Let $M$ be a NDTM (non deterministic Turing machine) which decides a certain NP-complete language, say SAT.

$M$ computes any instance $I$ of SAT in at most $p(n)$ non deterministic steps ($p$ in a polynomial function, $n$ is the input size). The length of a computation path can be measured as the rank of the non deterministic step where $M$ halts. Let call $rank_M(I)$ this rank ($rank_M(I)$ is $p(n)+1$ if $M$ rejects $I$).

What is the complexity of finding $ rank_M(I)$ for a given instance $I$ ? Or, what is the complexity of the corresponding decision problem : Given a boolean expression $I$, is it true that $rank_M(I)=k$ ? ($k$ is polynomially bounded in $n$)

The question deals with ranking more than counting (the output looks like rather an ordinal than a cardinal number), and I wonder whether some previous works have been done on the subject (please give me any related reference).

Thank you.