7
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ Please check Mahaney’s theorem and its generalizations. This blog article by Lance Fortnow is one of the good starting points. $\endgroup$
    – Tsuyoshi Ito
    May 9, 2012 at 22:52
  • 1
    $\begingroup$ @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) $\endgroup$
    – Sasho Nikolov
    May 10, 2012 at 0:04
  • $\begingroup$ @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. $\endgroup$
    – Ankur
    May 10, 2012 at 0:32
  • $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    May 10, 2012 at 0:35
  • 3
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    May 10, 2012 at 0:36

1 Answer 1

Reset to default
9
$\begingroup$

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 by Lance Fortnow for a nice explanation of Mahaney’s theorem and related results.

Improve this answer
$\endgroup$
8
  • 4
    $\begingroup$ and a proof: blog.computationalcomplexity.org/2011/09/mahaneys-theorem.html $\endgroup$
    – Sasho Nikolov
    May 10, 2012 at 1:03
  • $\begingroup$ 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. $\endgroup$
    – vzn
    May 11, 2012 at 2:06
  • $\begingroup$ @vzn: I understood that the domain of the problem is a sparse set from the example written in the last paragraph of the question. $\endgroup$
    – Tsuyoshi Ito
    May 11, 2012 at 2:28
  • $\begingroup$ so how about a proof? $\endgroup$
    – vzn
    May 11, 2012 at 4:33
  • $\begingroup$ @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? $\endgroup$
    – Ankur
    May 12, 2012 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.