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?

  • 2
    $\begingroup$ 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. $\endgroup$ – dkaeae Jan 22 at 15:05
  • $\begingroup$ @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. $\endgroup$ – Recursively Primitive Jan 23 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.