1
$\begingroup$

We have a set of possible "key"s $S$ represented by bitstrings of length $k$. In other words, $S$ contains an arbitrary subset of all bitstrings of length $k$. For example, when $k=3$, it can be $S = \{001, 010, 011, 000, 111\}$. I would like to find a "guess", which maximizes the Hamming distance of itself and the possible keys, assuming that the keys in $S$ are drawn with equal possibility. For instance, say the guess is $g = 001$, then the Hamming distances are $H(001, 001) = 0$, $H(001, 010) = 2$, $H(001, 011) = 1$, $H(001, 000) = 1$, and $H(001, 111) = 2$. It follows that the entropy is $E = -\left[\frac{1}{5}\log(\frac{1}{5})+\frac{2}{5}\log(\frac{2}{5})+\frac{2}{5}\log(\frac{2}{5})\right]$. A superior guess would be $g = 000$ or $g = 111$, which actually maximizes the entropy. There will be multiple guesses that maximize the entropy, and finding any of them is enough.

I actually have two related questions:

  1. How hard is it to find an optimal guess that maximizes the entropy? (In terms of N/NP/NPC/NPH, etc)
  2. How hard is it to find the maximum entropy?

I have previously posted a related question on math.SE, and a comment suggested that full enumeration is probably the best algorithm I can get. The problem sounds even harder than the $k$-partition problem, so I guess it is NP-complete or NP-hard.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.