# Techniques for proving NP completeness for a specific sequence of instances

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.

• Please check Mahaney’s theorem and its generalizations. This blog article by Lance Fortnow is one of the good starting points. – Tsuyoshi Ito May 9 '12 at 22:52
• @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 May 10 '12 at 0:04
• @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 May 10 '12 at 0:32
• @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 May 10 '12 at 0:35
• 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 May 10 '12 at 0:36