1
$\begingroup$

Let consider a problem of optimal covering of Hamming space.

So we have Hamming space $\{0,1\}^n$ and some integer $r$. We want to find a set $A \subseteq \{0,1\}^n$ such that any point from $\{0,1\}^n$ belong to $V_r(x)$ - full-sphere with center $x \in A$ and radius $r$ (with respect of Hamming metric).

We know that there is optimal covering i. e. such that $|A|\cdot |V_r| = 2^n\cdot Poly(n)$:

let $k = n - \log_2|V_r|$ then a random map from $\{0,1\}^k \to \{0,1\}^n$ defines optimal covering with positive probability.

But we don't know how this can be construct i.e. we don't know any $f$ that can be calculated in polynomial of $n$ time such that $ f: \{0,1\}^k \to \{0,1\}^n$ defines optimal covering.

My question is: whether there is such $f$ that can be calculated by using polynomaial of $n$ memory?

Improve this question
$\endgroup$
3
  • $\begingroup$ It might be helpful to re-state your problem in the following spirit: find an (easily computable) function $f\colon\{0,1\}^k\to\{0,1\}^{k+l}$ such that ${\rm Im}\,f+B_r=\{0,1\}^{k+l}$, where $B_r$ is the origin-centered unit ball of radius $r$. The dependence of $l$ and $r$ on $k$ must be stated very explicitly. $\endgroup$
    – Seva
    Commented Feb 27, 2015 at 16:15
  • $\begingroup$ Your notation at the end isn't great because P and PSPACE are classes of languages, not of functions. But anyway it is clear that you mean "algorithms in polynomial time (space)", except: what is the size of the input in this problem? E.g. do you want to run in time polynomial in $n$ (so we could say that the input is $n$ written in unary)? $\endgroup$
    – usul
    Commented Feb 27, 2015 at 18:27
  • $\begingroup$ Yes, polynomial of $n$ $\endgroup$
    – Alexey Milovanov
    Commented Feb 27, 2015 at 18:32

1 Answer 1

Reset to default
2
$\begingroup$

Yes,there is such $f$. By paper "Good covering of Hamming spaces with spherers" (http://www.renyi.hu/~pfrankl/j29.pdf) there is subspace in $\{0,1\}^n$ that define optimal covering. So, we can search all subspaces by using polynomial time machine that find optimal covering.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .