<p>If I understand the question correctly, I think that you are essentially asking whether a problem can be NP-hard even when it is defined on a sparse set of input strings.  If your notion of NP-hardness is under polynomial-time many-one reducibility, such a problem cannot exist (unless P=NP) because of Mahaney’s theorem.</p>

<p>See a <a href="http://blog.computationalcomplexity.org/2006/04/favorite-theorems-small-sets.html">blog article about Mahaney’s theorem</a> by Lance Fortnow for a nice explanation of Mahaney’s theorem and related results.</p>

CC BY-SA 3.0
2012-05-10T01:03:47.970Z
and a proof: http://blog.computationalcomplexity.org/2011/09/mahaneys-theorem.html
Sasho Nikolov
CC BY-SA 3.0
2012-05-11T02:06:55.837Z
this is a useful thm that should be more widely known/taught but dont see what in the original statement indicates that questioner is spec. working with sparse sets. its a useful "basic check" but the thm has no implication if one is not working with them.
vzn
CC BY-SA 3.0
2012-05-11T02:28:22.083Z
@vzn: I understood that the domain of the problem is a sparse set from the example written in the last paragraph of the question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-11T04:33:53.953Z
so how about a proof?
vzn
CC BY-SA 3.0
2012-05-12T16:17:28.750Z
@TsuyoshiIto I pondered over the argument and have the same question as vzn. The complexity of the problem = complexity of encoding in binary strings X computational complexity of the resulting language. Typically the encoding is at most polynomial in the size of the problem. One can take an arbitrary set of instances and encode it as a sparse language; but then complexity of the encoding is no more polynomial. How do I argue that the specific instances I am trying to assess the complexity of (in this case integer programs) under polynomial encoding can be expressed only as a sparse language?
Ankur
CC BY-SA 3.0
2012-05-12T16:27:57.300Z
@Ankur: The complexity of the problem depends on the input encoding of the problem, because it is measured in terms of the input length.  So as long as complexity is concerned, one problem with two different input encodings is in fact two different problems.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-12T16:40:38.657Z
@TsuyoshiIto I see. So when a statement is made saying that a problem such as independent set on a certain set of graph instances is NPC, what is the underlying encoding that is assumed? If I want to say that my set of problems is not NPC, for what encoding do I say this for the result to be meaningful? I am sorry I am not from the TCS community; these  are basic foundational/convention-related issues that I am not aware of. I would be appreciate if you can supplement your answer with a proof of sparsity.
Ankur
CC BY-SA 3.0
2012-05-12T16:47:40.083Z
@Ankur: I do not want to continue this discussion on cstheory.stackexchange.com, because the website is about research-level questions.  If you have further questions, you can search on cs.stackexchange.com and ask there if they are not already asked.  Then hopefully someone there can answer.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-10T00:57:11.773Z
2012-05-10T00:57:11.773Z
Tsuyoshi Ito
<p>Most NP-completeness proofs I have seen pertain to proving that a problem on a class of instances is NP-complete. E.g., satisfiability is NP-complete on the class of instances with clauses having three literals. Usually these proofs exploit the room that the definition of the class allows to reduce every instance from a known NP-complete class to an instance in the class of interest.</p>

<p>The question I am interested in is somewhat nonstandard: suppose I have a sequence of instances $P_1,P_2,...$ with size of input $n_1,n_2,...$. The size  $n_k \rightarrow \infty$ as $k\rightarrow \infty$. I want to claim that this specific sequence of instances is NP-complete. I know the instances are in NP, only NP-hardness remains to be shown. </p>

<p>Here's the challenge. Because I have a specific instance for each $k$, I don't have adequate room in the definition to reduce the known broad classes to this class. Furthermore, the sizes of my instances are also fixed, which restricts me further. Conceptually, I think I will have to argue that for every instance in some NP-complete class, there exists a $k$ such that this instance reduces to $P_k$. But I am not aware of techniques that reduce known instances to instances of interest with such specificity. </p>

<p>So my question is: are there techniques for proving NP-completeness/NP-hardness type results for a specific sequence of instances? </p>

<p>In case it helps, the instances $P_k$ are 0-1 integer programming problems with specific constants; in fact the constraint matrix of $P_k$ contains that of $P_{k-1}$ as a submatrix for all $k$ and the number of variables $n_k = 2^k$. Notice also that the set of instances $P_k$ has cardinality of $\mathbb{N}$, which is also the cardinality of the number of SAT instances (or finite graphs, or integer programs etc); thus as far as I understand, there is nothing in principle preventing my sequence instances from being NP-complete. </p>

CC BY-SA 3.0
2012-05-09T22:52:22.267Z
Please check Mahaney’s theorem and its generalizations.  [This blog article](http://blog.computationalcomplexity.org/2006/04/favorite-theorems-small-sets.html) by Lance Fortnow is one of the good starting points.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-10T00:04:17.357Z
@TsuyoshiIto: comment -> answer? or do you think the question will be closed? it's sort of elementary, but then again Mahaney's theorem may not be so widely known anymore (and there was another discussion about that on Lance's blog)
Sasho Nikolov
CC BY-SA 3.0
2012-05-10T00:32:11.227Z
@TsuyoshiIto thanks for the pointer.

Sasho and mods: I was not aware of Mahaney's theorem. It appears that Tsuyoshi's comment answers the question. I am sorry the question was elementary. I'd request you to archive it nonetheless since there may be other's like me (coming from the continuous math community) who know only the standard results from computational complexity, and in particular not know of Mahaney's theorem.
Ankur
CC BY-SA 3.0
2012-05-10T00:35:26.310Z
@Sasho Nikolov: I posted it as a comment because I thought that the question was too elementary, but I think that you have a good point that Mahaney’s theorem is not widely known.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-10T00:36:12.813Z
I'd prefer it if the comment were made an answer. The question is well formed and the fact that the answer is immediate doesn't invalidate the question itself.
Suresh Venkat
<cc.complexity-theory><reference-request><np-hardness><complexity-classes>
Techniques for proving NP completeness for a specific sequence of instances
Ankur
# Techniques for proving NP completeness for a specific sequence of instances

(Asked by: username_0 on 2012-05-09)

Most NP-completeness proofs I have seen pertain to proving that a problem on a class of instances is NP-complete. E.g., satisfiability is NP-complete on the class of instances with clauses having three literals. Usually these proofs exploit the room that the definition of the class allows to reduce every instance from a known NP-complete class to an instance in the class of interest.

The question I am interested in is somewhat nonstandard: suppose I have a sequence of instances $P\_1,P\_2,...$ with size of input $n\_1,n\_2,...$. The size $n\_k \rightarrow \infty$ as $k\rightarrow \infty$. I want to claim that this specific sequence of instances is NP-complete. I know the instances are in NP, only NP-hardness remains to be shown.

Here's the challenge. Because I have a specific instance for each $k$, I don't have adequate room in the definition to reduce the known broad classes to this class. Furthermore, the sizes of my instances are also fixed, which restricts me further. Conceptually, I think I will have to argue that for every instance in some NP-complete class, there exists a $k$ such that this instance reduces to $P\_k$. But I am not aware of techniques that reduce known instances to instances of interest with such specificity.

So my question is: are there techniques for proving NP-completeness/NP-hardness type results for a specific sequence of instances?

In case it helps, the instances $P\_k$ are 0-1 integer programming problems with specific constants; in fact the constraint matrix of $P\_k$ contains that of $P\_{k-1}$ as a submatrix for all $k$ and the number of variables $n\_k = 2^k$. Notice also that the set of instances $P\_k$ has cardinality of $\mathbb{N}$, which is also the cardinality of the number of SAT instances (or finite graphs, or integer programs etc); thus as far as I understand, there is nothing in principle preventing my sequence instances from being NP-complete.

**Tags:** cc.complexity-theory, reference-request, np-hardness, complexity-classes
> **Comments:**
> **username_1**: Please check Mahaney’s theorem and its generalizations.  [This blog article](http://blog.computationalcomplexity.org/2006/04/favorite-theorems-small-sets.html) by Lance Fortnow is one of the good starting points.  
> **username_2**: @TsuyoshiIto: comment -> answer? or do you think the question will be closed? it's sort of elementary, but then again Mahaney's theorem may not be so widely known anymore (and there was another discussion about that on Lance's blog)  
> **username_0**: @TsuyoshiIto thanks for the pointer.  Sasho and mods: I was not aware of Mahaney's theorem. It appears that Tsuyoshi's comment answers the question. I am sorry the question was elementary. I'd request you to archive it nonetheless since there may be other's like me (coming from the continuous math community) who know only the standard results from computational complexity, and in particular not know of Mahaney's theorem.  
> **username_1**: @Sasho Nikolov: I posted it as a comment because I thought that the question was too elementary, but I think that you have a good point that Mahaney’s theorem is not widely known.  
> **username_3**: I'd prefer it if the comment were made an answer. The question is well formed and the fact that the answer is immediate doesn't invalidate the question itself.  

---

## 1 answers

### Answer by username_1 on 2012-05-10. Score: 9 | Accepted answer

If I understand the question correctly, I think that you are essentially asking whether a problem can be NP-hard even when it is defined on a sparse set of input strings. If your notion of NP-hardness is under polynomial-time many-one reducibility, such a problem cannot exist (unless P=NP) because of Mahaney’s theorem.

See a [blog article about Mahaney’s theorem](http://blog.computationalcomplexity.org/2006/04/favorite-theorems-small-sets.html) by Lance Fortnow for a nice explanation of Mahaney’s theorem and related results.

> **Comments:**
> **username_2**: and a proof: http://blog.computationalcomplexity.org/2011/09/mahaneys-theorem.html  
> **username_4**: this is a useful thm that should be more widely known/taught but dont see what in the original statement indicates that questioner is spec. working with sparse sets. its a useful "basic check" but the thm has no implication if one is not working with them.  
> **username_1**: @vzn: I understood that the domain of the problem is a sparse set from the example written in the last paragraph of the question.  
> **username_4**: so how about a proof?  
> **username_0**: @TsuyoshiIto I pondered over the argument and have the same question as vzn. The complexity of the problem = complexity of encoding in binary strings X computational complexity of the resulting language. Typically the encoding is at most polynomial in the size of the problem. One can take an arbitrary set of instances and encode it as a sparse language; but then complexity of the encoding is no more polynomial. How do I argue that the specific instances I am trying to assess the complexity of (in this case integer programs) under polynomial encoding can be expressed only as a sparse language?  
> **username_1**: @Ankur: The complexity of the problem depends on the input encoding of the problem, because it is measured in terms of the input length.  So as long as complexity is concerned, one problem with two different input encodings is in fact two different problems.  
> **username_0**: @TsuyoshiIto I see. So when a statement is made saying that a problem such as independent set on a certain set of graph instances is NPC, what is the underlying encoding that is assumed? If I want to say that my set of problems is not NPC, for what encoding do I say this for the result to be meaningful? I am sorry I am not from the TCS community; these  are basic foundational/convention-related issues that I am not aware of. I would be appreciate if you can supplement your answer with a proof of sparsity.  
> **username_1**: @Ankur: I do not want to continue this discussion on cstheory.stackexchange.com, because the website is about research-level questions.  If you have further questions, you can search on cs.stackexchange.com and ask there if they are not already asked.  Then hopefully someone there can answer.  

---

