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

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

<ul>
<li><em>Approximable problems</em> - 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 <a href="http://en.wikipedia.org/wiki/Vertex_cover" rel="noreferrer">Vertex Cover</a> within a factor of $2$ of optimal, although the optimal answer is NP-complete.</li>
<li><em>Somewhat approximable problems</em> - NP-complete problems that can be approximated, but not within a constant factor.  The classic example is the <a href="http://en.wikipedia.org/wiki/Set_cover_problem" rel="noreferrer">set cover problem</a>, 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).</li>
<li><em>Unapproximable problems</em> - 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 <a href="http://en.wikipedia.org/wiki/Maximum_clique_problem" rel="noreferrer">max-clique</a> problem.</li>
<li><em>Fixed-parameter tractable</em> - 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$.</li>
</ul>

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

CC BY-SA 3.0
2014-06-13T19:50:31.477Z
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.
CC BY-SA 3.0
2014-06-13T20:01:39.793Z
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
CC BY-SA 3.0
2014-06-13T20:07:26.000Z
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.
CC BY-SA 3.0
2014-06-13T20:12:34.753Z
Sorry ... I don't understand your comment.
Ari Trachtenberg
CC BY-SA 3.0
2014-06-13T20:16:12.700Z
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.
CC BY-SA 3.0
2014-06-13T20:27:56.817Z
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.
CC BY-SA 3.0
2016-12-18T00:36:02.497Z
No.  I never implied that.
Ari Trachtenberg
CC BY-SA 3.0
2014-06-13T19:41:04.403Z
2014-06-13T19:41:04.403Z
Ari Trachtenberg
<p>Following previous questions <a href="https://cstheory.stackexchange.com/questions/21053/can-on-every-instance-p-np">here</a> and <a href="https://cstheory.stackexchange.com/questions/24878/any-result-connecting-an-np-complete-problem-with-slight-super-polynomial-time">here</a> around $NP$-complete problems (and P vs NP).</p>

<p>Are there "<em>easier</em>" or "<em>harder</em>" (sets of) instances of an $NP$-complete problem?</p>

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

<p>A <em>conjecture</em>  (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).</p>

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

<p>Thankx</p>

CC BY-SA 3.0
2014-06-14T01:17:16.840Z
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](http://staff.science.uva.nl/~leen/PDFpapers/434.pdf). In particular take a look to the *instance complexity* and *resource-bounded instance complexity*. See also: Mundhenk, [Instance Complexity of NP-hard sets](http://www.minet.uni-jena.de/fakultaet/mundhenk/papers/jim99.ps) (1999) for some developments (I would also like to know what is the current status of that line of research).
Marzio De Biasi
CC BY-SA 3.0
2014-06-14T01:21:50.623Z
@MarzioDeBiasi ahh great, will definately take a look there, thanks
Nikos M.
CC BY-SA 3.0
2014-06-14T01:36:32.510Z
@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.
CC BY-SA 3.0
2014-06-14T08:35:14.043Z
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
CC BY-SA 3.0
2014-06-14T14:38:19.320Z
@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.
<np-complete><hard-instances>
Easier and Harder instances of NP-complete problems?
Nikos M.
# Easier and Harder instances of NP-complete problems?

(Asked by: username_0 on 2014-06-13)

Following previous questions [here](https://cstheory.stackexchange.com/questions/21053/can-on-every-instance-p-np) and [here](https://cstheory.stackexchange.com/questions/24878/any-result-connecting-an-np-complete-problem-with-slight-super-polynomial-time) 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

**Tags:** np-complete, hard-instances
> **Comments:**
> **username_1**: 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](http://staff.science.uva.nl/~leen/PDFpapers/434.pdf). In particular take a look to the *instance complexity* and *resource-bounded instance complexity*. See also: Mundhenk, [Instance Complexity of NP-hard sets](http://www.minet.uni-jena.de/fakultaet/mundhenk/papers/jim99.ps) (1999) for some developments (I would also like to know what is the current status of that line of research).  
> **username_0**: @MarzioDeBiasi ahh great, will definately take a look there, thanks  
> **username_0**: @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?  
> **username_1**: 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.  
> **username_0**: @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...  

---

## 1 answers

### Answer by username_2 on 2014-06-13. Score: 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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Maximum_clique_problem) 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.

> **Comments:**
> **username_0**: 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.  
> **username_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.  
> **username_0**: 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*)  
> **username_2**: Sorry ... I don't understand your comment.  
> **username_0**: 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  
> **username_0**: 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?  
> **username_2**: No.  I never implied that.  

---

