For a graph $G=(V,E)$, I build an adjacency matrix and encode it into binary, clearly.

Now, imagine the alphabet I am given is $\Sigma=\{1\}$, is there a way for me to encode any graph instance with such alphabet?

In my reasoning, I think you can, since if you can map any binary string, to a unary string, then you can transitively mapping one adjacency matrix to a unary string, hence a graph. Does this reasoning have any flaw? Is this a valid argument?

  • 1
    $\begingroup$ Why do you think it's not a solid argument? $\endgroup$ – Raphael Apr 29 '15 at 16:44
  • $\begingroup$ What makes me doubt is the fact that to generate an encoding I have to try out all the different encoding up until the one I need. So to give you an example, to encode a graph, I have to iterate through all the graphs until I meet one that unary number that encodes it $\endgroup$ – revisingcomplexity Apr 29 '15 at 16:46
  • 3
    $\begingroup$ No, you can encode and decode directly by converting between binary and unary. $\endgroup$ – Yuval Filmus Apr 29 '15 at 17:35

As you mention in your question, everything that can be coded in binary (that is, every countable set) can also be encoded in unary. Arrange all binary strings in some order, say $$ \epsilon, 0, 1, 00, 01, 10, 11, \ldots. $$ Let $w_i$ be the $i$th string in this order. You can convert from binary to unary by mapping $w_i$ to $1^i$ and vice versa.

You mention that you are worried that this encoding is not efficient. From the perspective of complexity theory, this is not so clear, since if your representation is very large, then it is fair to allow you a lot of time to encode and decode it. In formal terms, for a representation of length $n$, you should be able to encode and decode in time polynomial in $n$.

Consider the example of graphs. In order to encode a graph in unary, you first encode it in binary, say using $m$ bits. Then you output $1^n$ for some $n \approx 2^m$. You can easily compute the output in time polynomial in $n$. Going the other way around, you can convert $1^n$ to the corresponding binary string $w_n$ in time polynomial in $n$ as well, and decoding the binary representation only takes time polynomial in $m = O(\log n)$.

  • $\begingroup$ Instead of mapping $w_i \mapsto 1^i$ (which requires you to find determine the number of your input in that list) you can use the simpler $w \mapsto 1^{w_2}$. That's not bijective, though. $\endgroup$ – Raphael Apr 29 '15 at 17:58

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.