2
$\begingroup$

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?

$\endgroup$
  • 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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.