# 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>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$?

• For problems which are in P for fixed $k$ there is a term fixed-parameter tractable. It sounds like you're looking for a term for the next class up from that in a hierarchy. – Peter Taylor May 9 '18 at 11:14
• @PeterTaylor Yeah that does seem similar. Basically you have some parameter that tells you how long an answer you are looking for, but the problem has a polynomial length certificate (rather than polynomial time solution) after adjusting for that parameter – The C May 9 '18 at 16:22
• Maybe it's best just to show the problem I'm looking at is NP hard (which I can do even restricting to the case where $k$ is linear in the size of the objects themselves) and forget about the certificate. – The C May 9 '18 at 16:25

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.

• "No, you don't say it is NP for any fixed k, since that's not right" - What do you mean? If you fix k then the problem "Are two objects related by k moves" is in NP – The C May 9 '18 at 16:16
• The point is that the certificate is polynomial with respect to the size of the two objects, but might be very long because of the number of moves. But the latter is in a sense less important because if you are asking to see if they are related by $k$ moves, you cannot expect an answer better than linear in $k$. – The C May 9 '18 at 16:19

In many cases, if you have n objects, then either there is a sequence of at most n-1 moves getting you from A to B, or there is none. This will be clearly in NP.

If you have rules for the moves so that there can be a shortest route with length that is not polynomial in n, then it may be the case that the problem is not in NP.

The same would be the case if the move rules are so complicated that you cannot find whether moving from X to Y is allowed in polynomial time in n.

Remember that to prove that the problem is NP-hard, you need (roughly) to prove that if you are able to solve each "YES" instance in polynomial time, then you can also solve each "YES" instance of some NP-complete problem in polynomial time. And NP-complete just means "NP-hard, but also in NP".

• I see, I guess I should just show it is np hard and be done with it. I can mention it is np complete if you disallow moves that make the objects more complicated. – The C May 9 '18 at 16:56