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).
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.)
External links referenced by this document:
Local articles referenced by this article: