We consider binary strings of length n and we consider the distance between two strings x and y, d(x,y), to be the Hamming distance, i.e. the number of mismatches. For some fixed n and d, what is the size of the largest set S of strings with the property that, for any two strings x and y in S, d(x,y) >= d?
This problem is equivalent to the graph theoretic problem "Max Distant Set" on an n-dimensional hypercube. Max Distant Set asks, what is the size of the largest vertex subset such that no two vertices in that set are at distance less than d from each other. When d = 2, Max Distant Set is equivalent to Max Independent Set.
Also, what is the size of this set for alphabets of size k > 2? E.g. what if the strings are quaternary (as in DNA)?
This problem is extremely important to coding theory. When sending a code from such a set, the correct code can be retrieved even if up to ceiling(d/2 - 1) bits are changed. The problem has therefore been extremely well studied. This excellent resource maintained by Litsyn, Rains, and Sloane contains many results and references for this problem.
What we want to know is, given n and d, how hard is it to find the size of the largest set? Is this problem NP-complete in the general case or is there a pseudopolynomial algorithm to solve it?