4

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

Community
  • 1
Nikos M.
  • 581
  • 2
  • 9
  • 2
    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 01:17
  • @MarzioDeBiasi ahh great, will definately take a look there, thanks – Nikos M. Jun 14 '14 at 01: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 01: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 08: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

1 Answers1

6

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.

Ari Trachtenberg
  • 282
  • 1
  • 5
  • 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
  • 2
    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
  • let me answer my own question here, your answer implies that for example the max-clique problem every poly-reduction maps (all) hard-instances to equally hard instances of another problem (in a sense of the classes you mention). Is this correct comprehension of your answer? – Nikos M. Jun 13 '14 at 20:27
  • 1
    No. I never implied that. – Ari Trachtenberg Dec 18 '16 at 00:36