<p><a href="http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming_solution">Knapsack</a> problem. It can be solved in polytime by dynamic programming if you give the target weight in unary.</p>

<p>Similarly other problems which are weekly polynomial time (<a href="http://en.wikipedia.org/wiki/Pseudo-polynomial_time">pseudo-polynomial time</a>) but not strongly polynomial time would need some part of input to be in unary. (You may also want to search for <a href="http://en.wikipedia.org/wiki/Weakly_NP-complete">weakly NP-complete</a>.)</p>

CC BY-SA 2.5
2010-11-18T14:13:03.007Z
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. :)
Daniel Apon
CC BY-SA 2.5
2010-11-18T14:24:10.533Z
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!
Daniel Apon
CC BY-SA 2.5
2010-11-18T03:15:16.693Z
2010-11-18T03:15:16.693Z
Kaveh
<p>The &quot;Generic Machine Simulation Problem&quot; (GMSP) when encoded with a mix of binary and unary is a P-complete problem. &quot;Limits to Parallel Computation&quot; by Greenlaw, Hoover, Ruzzo pg 58. (Problem A.12.1)</p>
<blockquote>
<p>Given: A string <span class="math-container">$x$</span>, a description <span class="math-container">$M$</span> of a Turing machine <span class="math-container">$M$</span>, and an integer <span class="math-container">$t$</span> coded in <em>unary</em>. (To be precise, the input is the string <span class="math-container">$x\# M\#^t$</span>, where <span class="math-container">$\#$</span> is a delimiter character not otherwise present in the string.)</p>
<p>Problem: Does <span class="math-container">$M$</span> accept <span class="math-container">$x$</span> within <span class="math-container">$t$</span> steps?</p>
</blockquote>
<p>If <span class="math-container">$t$</span> is not encoded in unary (i.e. binary) then <span class="math-container">$t$</span> could be a number exponentialy bigger than <span class="math-container">$n$</span> and so the simulation could take exponential time.</p>

CC BY-SA 2.5
2010-11-17T15:48:57.300Z
2010-11-17T15:48:57.300Z
2020-06-17T09:38:08.363Z
Niall Murphy
<p>As a mild follow-up to <a href="https://cstheory.stackexchange.com/questions/2935/examples-in-which-the-size-of-the-alphabet-geq-2-used-for-an-encoding-matter">this question on alphabet sizes</a>, let me ask about the other part of the natural numbers, i.e. $\le 2$.</p>

<p>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.</p>

<blockquote>
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!)
</blockquote>

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

CC BY-SA 2.5
2010-11-17T10:54:53.953Z
I would have thought the unary inputs would dominate; if not, then there is no reason to use this representation in the first place.
András Salamon
CC BY-SA 2.5
2010-11-17T11:09:53.713Z
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.
Daniel Apon
CC BY-SA 2.5
2010-11-17T11:12:03.053Z
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.
Daniel Apon
CC BY-SA 2.5
2010-11-17T11:17:42.257Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-17T11:23:22.937Z
@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.
Daniel Apon
<cc.complexity-theory><turing-machines>
Problems with mixed unary/binary inputs
Daniel Apon
# Problems with mixed unary/binary inputs

(Asked by: username_0 on 2010-11-17)

As a mild follow-up to [this question on alphabet sizes](https://cstheory.stackexchange.com/questions/2935/examples-in-which-the-size-of-the-alphabet-geq-2-used-for-an-encoding-matter), 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).

**Tags:** cc.complexity-theory, turing-machines

> **Comments:**
> **username_1**: I would have thought the unary inputs would dominate; if not, then there is no reason to use this representation in the first place.  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: @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.  

---

## 2 answers

### Answer by username_3 on 2010-11-18. Score: 6 | Accepted answer

[Knapsack](http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming_solution) 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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Weakly_NP-complete).)

> **Comments:**
> **username_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. :)  
> **username_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!  

---

### Answer by username_4 on 2010-11-17. Score: 4

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.


---

