2
$\begingroup$

I'm searching the space of length $n$ strings (a-z lowercase), which I suppose we could represent as a large graph of strings and hamming distances between the strings.

I'm given some pairs of strings and distances $v_i, d_i$ . I need to find a string which has distance $d_i$ from each each string $v_i$ .

Does there exist an efficient algorithm for finding this? Perhaps it's possible to triangulate to the right string?

Improve this question
$\endgroup$
4
  • $\begingroup$ How many pairs do you have? The problem might become simpler if you have only a few pairs. $\endgroup$
    – Yuval Filmus
    Nov 20, 2017 at 19:34
  • $\begingroup$ I'm dealing with a variant of mastermind where you can make a guess against the true string and find out the distance of that guess. Goal is to minimize number of guesses. In my experience trying a greedy guess approach, it takes a few dozen guesses for a string of length 10-15. $\endgroup$
    – user2623492
    Nov 20, 2017 at 19:39
  • 1
    $\begingroup$ You should include all information relevant to your question in your post. Otherwise we will provide an answer which won't satisfy you, you will modify your question, we will have to provide another answer which won't satisfy you, and so on. $\endgroup$
    – Yuval Filmus
    Nov 20, 2017 at 19:40
  • $\begingroup$ I was specifically interested in my original question rather than a discussion of strategies for this game. If you feel I should reformulate the question completely, should I make a new one? $\endgroup$
    – user2623492
    Nov 20, 2017 at 19:43

1 Answer 1

Reset to default
2
$\begingroup$

Your problem is likely hard. I will consider a decision version of your problem in which the goal is to ask whether there exists any solution. I will show that the binary variant is NP-complete, and the same ideas probably imply that this decision version of your problem is also NP-complete.

Other decision versions of your problem are likely also hard, though perhaps not NP-hard. For example, consider the problem in which you are promised that a unique solution exists, and your goal is to determine the value of its first bit. This problem cannot be NP-hard since it has the same complexity as its complement. Nevertheless, it is probably hard in some other, appropriate sense.

The decision version of your problem that I will analyze asks whether there is an answer. The problem is clearly in NP, and we prove that it is NP-hard by reduction from X3SAT, a variant of 3SAT in which a formula is satisfiable if every clause contains exactly one satisfied literal. Given a 3CNF on $n$ variables $x_1,\ldots,x_n$, we will consider strings of length $2n$ which encode a truth assignment: a 1 in position $2(i-1)+1$ encodes that $x_i$ is true, and a 1 in position $2(i-1)+2$ encodes that $x_i$ is false.

In order to force that any solution must have exactly one 1 in each of the positions $2(i-1)+1,2(i-1)+2$, we ask that it have distance $n$ from the strings $(00)^n$ and $(00)^{i-1}(11)(00)^{n-i}$ for $1 \leq i \leq n$. In order to force any solution to satisfy all clauses, for every clause we take the string which has 1s in the positions corresponding to the literals in the clause, and we ask that the solution be at distance $(n-3)+2$ from this string. A string satisfies these $n+m+1$ constraints (where $m$ is the number of clauses) if and only if it is a satisfying assignment to the given 3CNF.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thank you!! One question: what do you mean by the complement of the first bit variant? $\endgroup$
    – user2623492
    Nov 20, 2017 at 20:19
  • $\begingroup$ Asking whether the first bit is 0 can be reduced to asking whether the first bit is 1 (by complementing all the strings), so the problem cannot be NP-hard unless NP=coNP. $\endgroup$
    – Yuval Filmus
    Nov 20, 2017 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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