Following previous questions here and here around $NP$-complete problems (and P vs NP).

Are there "easier" or "harder" (sets of) instances of an $NP$-complete problem?

If yes (which i assume), how a polynomial-time mapping between $NP$-complete problems maps between easier or harder (sets of) instances?

A conjecture (related to directions of previous questions) is that there should be considerable mapping betwen "easier" to "harder" and "harder" to "easier" (if i may, with probability almost 1).

PS. This in effect tries to study (a little more in depth) the role of polynomial-time mappings used in $NP$-complete reductions.


  • 2
    $\begingroup$ There is a lot of work on the subject (and many approaches); you can take a look to the (old but good) survey by Buhrman and Torenvliet: On the structure of complete sets. In particular take a look to the instance complexity and resource-bounded instance complexity. See also: Mundhenk, Instance Complexity of NP-hard sets (1999) for some developments (I would also like to know what is the current status of that line of research). $\endgroup$ Jun 14, 2014 at 1:17
  • $\begingroup$ @MarzioDeBiasi ahh great, will definately take a look there, thanks $\endgroup$
    – Nikos M.
    Jun 14, 2014 at 1:21
  • $\begingroup$ @MarzioDeBiasi, according to you, is this of any (current) relevance over P vs NP (i think it might be, as i stand on P=NP and relate to it in another way), what do you think? $\endgroup$
    – Nikos M.
    Jun 14, 2014 at 1:36
  • $\begingroup$ It is another approach to the problem: theorem 6.5 of Mindhenk's paper states that every recursive problem not in P can be characterized by hard instances (hard w.r.t. time bounded compressibility). At first glance (but I'm not an expert and I should think more about it), with this notion of instance hardness the NPC mappings cannot map "easy" instances to "hard" instances. $\endgroup$ Jun 14, 2014 at 8:35
  • $\begingroup$ @MarzioDeBiasi, yes this should be taken under consideration, related to it (from a quick look at the first paper), the issue of isomorphism between NPC problems is also important (it reminds me sth like the relativization barrier). Still reading the references... $\endgroup$
    – Nikos M.
    Jun 14, 2014 at 14:38

1 Answer 1


If P=NP, then all NP-complete problems are equally difficult from the perspective of polynomial-time reductions.

On the other hand, if P!=NP, then we have ways to differentiate NP-complete problems, for example:

  • Approximable problems - NP-complete problems where we can find a polynomial-time algorithm that gives us almost the desired answer (within a constant factor). For example, there is a trivial algorithm to produce a Vertex Cover within a factor of $2$ of optimal, although the optimal answer is NP-complete.
  • Somewhat approximable problems - NP-complete problems that can be approximated, but not within a constant factor. The classic example is the set cover problem, which can be approximated within a fraction of roughly $ln n$ for $n$ sets, but cannot be approximated with a less than logarithmic fraction (unless P=NP).
  • Unapproximable problems - NP-complete problems for which (under accepted assumptions) no polynomial-time algorithm exists that approximates the solution within any polynomial factor. An example is the max-clique problem.
  • Fixed-parameter tractable - problems that run in polynomial time if you fix one parameter. The classic example again is vertex-cover, which can be computed in time $O(2^k n)$ for a vertex cover of size $k$ in a graph of size $n$.

In short, under accepted assumptions, there are varying difficulties of NP-complete problems.

  • $\begingroup$ Please elaborate on "under accepted assumptions", as i think it pertains to the question. Equally difficult from the perspective of polynomial-time reductions, does not exclude levels of diificulty or easiness or mapping between different classes that you state in your answer. $\endgroup$
    – Nikos M.
    Jun 13, 2014 at 19:50
  • 2
    $\begingroup$ For max-clique, the assumption is that P!=NP (see <1>). If P=NP, then you can get from any NP problem to any other NP problem with a polynomial-time mapping. --- <1> Zuckerman, D. (2006), "Linear degree extractors and the inapproximability of max clique and chromatic number", Proc. 38th ACM Symp. Theory of Computing, pp. 681–690, doi:10.1145/1132516.1132612, ISBN 1-59593-134-1, ECCC TR05-100. $\endgroup$ Jun 13, 2014 at 20:01
  • $\begingroup$ For example let me elaborate, how does poly-reductions map between approximable instances of a problem to Somewhat approximable instances of another problem. Np-hard approximation is a general result, how does this pertain per instance? (maybe i am wrong but it involves a fixed approximation algorithm for every instance) $\endgroup$
    – Nikos M.
    Jun 13, 2014 at 20:07
  • $\begingroup$ Sorry ... I don't understand your comment. $\endgroup$ Jun 13, 2014 at 20:12
  • 1
    $\begingroup$ No. I never implied that. $\endgroup$ Dec 18, 2016 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.