# Easier and Harder instances of NP-complete problems?

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.

Thankx

• 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). – Marzio De Biasi Jun 14 '14 at 1:17
• @MarzioDeBiasi ahh great, will definately take a look there, thanks – Nikos M. Jun 14 '14 at 1:21
• @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? – Nikos M. Jun 14 '14 at 1:36
• 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. – Marzio De Biasi Jun 14 '14 at 8:35
• @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... – 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.

• 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. – Nikos M. Jun 13 '14 at 19:50
• 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. – Ari Trachtenberg Jun 13 '14 at 20:01
• 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) – Nikos M. Jun 13 '14 at 20:07
• Sorry ... I don't understand your comment. – Ari Trachtenberg Jun 13 '14 at 20:12
• 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 – Nikos M. Jun 13 '14 at 20:16