Theoretical Computer Science
cc.complexity-theory turing-machines
Updated Thu, 23 Jun 2022 17:48:54 GMT

Problems with mixed unary/binary inputs


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).




Solution

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.)





Comments (2)

  • +0 – 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. :) — Nov 18, 2010 at 14:13  
  • +0 – 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! — Nov 18, 2010 at 14:24