5
$\begingroup$

As a mild follow-up to this question on alphabet sizes, let me ask about the other part of the natural numbers, i.e. $\le 2$.

Clearly everyone knows about problems over a binary alphabet. Unary, on the other hand, is most commonly used in input encodings for a problem to a Turing machine (at least, that's the use I'm interested in). But, are there any good examples of problems where the input is encoded with an explicit mix of the two, perhaps in order to make a particular complexity argument? Admittedly, since many classes (like NP) are closed under concatenation, you could just append one such problem's input to another -- but I'm particularly interested in problems where the "natural" form of the problem requires a mix.

What are some problems where their standard input to a Turing machine is a mix of unary and binary encoding? (Bonus points if the only-unary or only-binary encoded versions are meaningful as well!)

P.S. I'm less interested in broad "classes of problems" (not to be confused with complexity classes), such as "any crypto problem" where there is frequently a security parameter of $1^n$ and the rest of the problem is in binary, or as Tsuyoshi points out, "any FPTAS". I'm very interested in specific computational problems that require both a unary and a binary component in the input for the problem to be meaningful (and perhaps, to be meaningful at all).

Improve this question
$\endgroup$
5
  • $\begingroup$ I would have thought the unary inputs would dominate; if not, then there is no reason to use this representation in the first place. $\endgroup$
    – András Salamon
    Commented Nov 17, 2010 at 10:54
  • $\begingroup$ Surprisingly this isn't the case with all problems... If one part of the input contains exponentially more information than another, but you want both to "factor in" equally toward the problem's complexity, this could be a reason to use a mixed input. Perhaps think of the swapping point from unary to binary as a succinct representation issue. $\endgroup$
    – Daniel Apon
    Commented Nov 17, 2010 at 11:09
  • $\begingroup$ Expanding on my leading postscript in the question... Case in point: You frequently need a security parameter of $1^n$ for crypto problems, while the rest of the problem is given in binary. This isn't the motivation for my question, but it's a great example in general. $\endgroup$
    – Daniel Apon
    Commented Nov 17, 2010 at 11:12
  • 2
    $\begingroup$ This may be similar to security parameter (which you explicitly state that you are less interested), but an FPTAS is a polynomial-time algorithm which receives the original input (in whatever format) and the unary representation of k∈ℕ and produces a (1+1/k)-approximation. $\endgroup$
    – Tsuyoshi Ito
    Commented Nov 17, 2010 at 11:17
  • $\begingroup$ @Tsuyoshi, that's actually a great point. However, I'm looking for specific computational problems -- nothing as broad as the classes of "all crypto problems" or "any FPTAS". I'll update my question to clarify. $\endgroup$
    – Daniel Apon
    Commented Nov 17, 2010 at 11:23

2 Answers 2

Reset to default
6
$\begingroup$

Knapsack problem. It can be solved in polytime by dynamic programming if you give the target weight in unary.

Similarly other problems which are weekly polynomial time (pseudo-polynomial time) but not strongly polynomial time would need some part of input to be in unary. (You may also want to search for weakly NP-complete.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Perfect! I've known the term "strongly NP-complete" for a while (though, I suppose, never the connection between binary/unary encodings), and while it makes sense now, I've never thought about "weakly NP-complete" problems. Thanks for patching a hole in my knowledge. :) $\endgroup$
    – Daniel Apon
    Commented Nov 18, 2010 at 14:13
  • $\begingroup$ In 20/20 hindsight, it turns out I was looking for a class of problems (oops). @Tsuyoshi's answer was actually headed in the right direction, and deserved more credit than I gave it! $\endgroup$
    – Daniel Apon
    Commented Nov 18, 2010 at 14:24
4
$\begingroup$

The "Generic Machine Simulation Problem" (GMSP) when encoded with a mix of binary and unary is a P-complete problem. "Limits to Parallel Computation" by Greenlaw, Hoover, Ruzzo pg 58. (Problem A.12.1)

Given: A string $x$, a description $M$ of a Turing machine $M$, and an integer $t$ coded in unary. (To be precise, the input is the string $x\# M\#^t$, where $\#$ is a delimiter character not otherwise present in the string.)

Problem: Does $M$ accept $x$ within $t$ steps?

If $t$ is not encoded in unary (i.e. binary) then $t$ could be a number exponentialy bigger than $n$ and so the simulation could take exponential time.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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