Conventions on NP regarding certificates with length exponential in a variable $k$ Non-computer scientist here.  Suppose you have a problem of the following general form:


  There is a class of objects, and a restricted set of moves to pass between objects.  It is known that all such objects are related by this set of moves.  There's a problem of the form "Given two objects $X_1$ and $X_2$, can you move between them in at most $k$ moves?"


An example would be where the objects are graphs on the same number of vertices, and the moves are deletion and addition of edges.  This question is obviously NP in the sense that you can just list the additions/deletions made to get a certificate.

Now the problem is if there is no a priori upper bound on how many moves you might need to move between two objects.  In the previous example, If the graphs have $n$ vertices then you need at most $n(n-1)/2$ additions/deletions to pass between any two graphs (going from $n$ disjoint vertices to the complete graph on $n$ vertices).  Thus, asking the question with very large $k&gt;n(n-1)/2$ can be answered easily, so the problem is in NP regardless of $k$.

However, if there is no such bound, then maybe $k$ could be very large compared to the size of your objects, requiring a large certificate compared to the size of the input (since $k$ only needs $\log k$ bits).  So if $k$ is fixed before the statement of the problem then it is in NP, but if $k$ is given together with the input then it is not.

What's the convention for dealing with this type of situation?  Do you just say that the problem is NP for any fixed $k$?
No, you don't say it is NP for any fixed k, since that's not right; NP means something specific, and that's not it.  Instead, I would suggest that you describe the situation, as you did, in a self-contained way, since your definition is different from the ones where we have existing terminology.