# Reducible from vertex cover for only some inputs

Suppose I have an NP problem, $$\text{PROBLEM}(n)$$, such that for certain values of $$n$$ I can get a reduction from vertex cover with $$n$$ vertices, and for others such a reduction is not possible (if $$\mathbf{P}\neq\mathbf{NP}$$).

More precisely, there exists an infinite set $$M\subseteq\mathbb{N}$$ such that for $$m\in M$$ we can obtain a reduction from vertex cover with $$m$$ vertices to $$\text{PROBLEM}(m)$$, while for others PROBLEM can be solved in "polynomial" time. (More precisely, there exists a polynomial $$p$$ such that for all $$n \in \mathbb{N} \setminus M$$, $$\text{PROBLEM}(n)$$ is solvable in under $$p(n)$$ steps.) $$M$$ is infinite, but can be arbitrarily sparse.

I'm at a loss as to what we can say about the complexity of the problem. If $$\mathbf{P}\neq \mathbf{NP}$$, there is no polynomial $$q$$ dominating the running time of PROBLEM because we can always pick a sufficiently large $$m\in M$$ that will exceed $$q(m)$$; however, neither do I see any way to show NP-completeness. The naive approach of taking an instance of vertex cover with $$n$$ vertices and padding it up to $$m\in M$$ does not work because we might not be able to reach $$m$$ in a polynomial number of steps due to the sparsity of $$M$$. Is this an example of a problem that's neither in $$\mathbf{P}$$ nor NP-hard?

• If your goal is simply to show $\mathbf{P} \neq \mathbf{NP}$ implies the existence of an NP-intermediate problem, then you should take a look at Richard Ladner's proof; otherwise, I believe the question would benefit from making it more clear in what ways PROBLEM differs from Ladner's construction and why such differences are interesting. – dkaeae Jan 22 at 15:05
• @dkaeae My goal is to confirm that I have no chance of obtaining an NP-completeness result for the problem. I can't really specify PROBLEM further because strictly speaking it's not a single problem but a family of them. There is a polynomial time black box in the computation that sometimes outputs parameters that make the problem easy, but sometimes enough to encode an NP-complete problem. If the routine outputs hard parameters only finitely often, then PROBLEM is in P, if it outputs hard parameters sufficiently often, it is NP-complete. I wasn't sure what happens in between the two. – Recursively Primitive Jan 23 at 10:13