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$ – Marzio De Biasi Jun 14 '14 at 1:17
  • $\begingroup$ @MarzioDeBiasi ahh great, will definately take a look there, thanks $\endgroup$ – Nikos M. Jun 14 '14 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 '14 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$ – Marzio De Biasi Jun 14 '14 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 '14 at 14:38

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 '14 at 19:50
  • 1
    $\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$ – Ari Trachtenberg Jun 13 '14 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 '14 at 20:07
  • $\begingroup$ Sorry ... I don't understand your comment. $\endgroup$ – Ari Trachtenberg Jun 13 '14 at 20:12
  • $\begingroup$ yeap, unfortunately me too dont have access to the paper you mention. Anyway, the question is about the study of the poly-reductions themselves on the NPC space, this can map easy (in a sense of one of the classes in the answer) instances to hard instances of some other problem, but since both easy and hard instances are part of a NPC problem this does not reduce a whole problem (into an easier one) but only some instances of it, hope this is more clear, regardless of P vs NP status $\endgroup$ – Nikos M. Jun 13 '14 at 20:16

Your Answer

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

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