<p>An example I like is the argument that $\mathrm{NE\subseteq coNE}/(n+1)$ by counting strings in the language (see e.g. <a href="https://blog.computationalcomplexity.org/2004/01/little-theorem.html" rel="noreferrer">https://blog.computationalcomplexity.org/2004/01/little-theorem.html</a>).</p>

CC BY-SA 3.0
2018-04-19T02:23:09.453Z
This is great, because it doesn't rely on the probabilistic method or look-up tables. Thanks for this.
Samuel Schlesinger
CC BY-SA 3.0
2018-04-19T02:45:08.313Z
I think advice classes are usually not defined to have exact advice length @RickyDemer
Samuel Schlesinger
CC BY-SA 3.0
2018-04-19T02:47:29.370Z
Also, I can't see this in my attempts so far, so if someone could give a reference or mention how to see it, I'd appreciate it
Samuel Schlesinger
CC BY-SA 3.0
2018-04-19T07:58:19.277Z
All right, so $2^n+1$ possible values make about $n+2^{-n}\le n+1$ bits.
Emil Jeřábek
CC BY-SA 3.0
2018-05-01T19:00:12.310Z
@SamuelSchlesinger: While P/poly or C/log (for any class C) are usually defined with advice length up to big-Oh, that's not always true. Some results use an exact number of advice bits (sometimes as small as 1!).
Joshua Grochow
CC BY-SA 3.0
2018-05-01T19:05:29.723Z
@JoshuaGrochow: right, thank you. I saw that recently while reading some of the work using the easy witness method in the early 2000s actually.
Samuel Schlesinger
CC BY-SA 3.0
2018-04-18T21:59:17.767Z
2018-04-19T08:05:49.937Z
2018-04-19T08:05:49.937Z
Emil Jeřábek
<p>One example is $\mathbf{NL} \subseteq \mathbf{UL}/\text{poly}$. This theorem was proven by Reinhardt and Allender in their paper <a href="http://ftp.cs.rutgers.edu/pub/allender/nlul.pdf" rel="noreferrer">"Making Nondeterminism Unambiguous"</a>. Without going into the details, the advice in their algorithm consists of a sequence of edge-weight assignments so that for any digraph $G$ encoded by an $n$-bit string, some assignment in the sequence makes $G$ "min-unique". Such a sequence can be shown to exist by the probabilistic method. Reinhardt and Allender's main contribution was to give unambiguous log-space algorithms for figuring out <em>which assignment</em> in the sequence works for a particular given digraph $G$ and for deciding $s$-$t$ connectivity on a min-unique digraph.</p>

<p>As with $\mathbf{BPP} \subseteq \mathbf{P}/\text{poly}$, it is conjectured that nonuniformity is not actually necessary here, i.e., it is conjectured that $\mathbf{NL} = \mathbf{UL}$.</p>

CC BY-SA 3.0
2018-04-18T20:05:55.790Z
2018-04-18T20:05:55.790Z
William Hoza
<p>I am not sure if it fits what you are looking for, but there are a few results proving hierarchy theorems for semantic complexity classes with one bit of advice, where no hierarchy theorem is known without advice. The best known example is BPP, for which we do not know a hierarchy theorem, but Fortnow and Santhanam showed one exists with one bit of advice (building on a result of Barak that used more advice). <a href="https://link.springer.com/article/10.1007/s00037-007-0227-8" rel="noreferrer">This article</a> by Melkebeek and Pervyshev gives references and the history, and a theorem that seems to subsume the previous ones.</p>

CC BY-SA 4.0
2018-05-22T18:02:42.770Z
If it is only one bit can't we just cycle through it like it case of $P/log$?
Turbo
CC BY-SA 4.0
2018-06-03T03:47:40.237Z
@Turbo Is your claim that BPP/1 is the same as BPP. Try to write down a proof and you should be able to easily see for yourself where this goes wrong
Sasho Nikolov
CC BY-SA 3.0
2018-04-19T14:52:17.590Z
2018-04-19T14:52:17.590Z
Sasho Nikolov
<p>I'm curious about ways in which you have seen non-uniformity be useful in computation. One way is randomness, as in $BPP \subseteq P/poly$, and another is look-up tables which are used to show that all languages have non-uniform circuits.</p>

<p>In particular, I'm interested in ways that objects known to exist via the probabilistic method and other non-constructive (or not-constructive-enough) proof methods can be leveraged using non-uniformity. I'd prefer the examples to be natural, not contrived. To be clear, a circuit for a contrived problem could be something like: given some language $L \in P$, I create a polynomial size circuit by computing some really hard function $f(|x|)$ using my advice and asking whether $f(|x|)^{n/|f(|x|)|} \oplus x \in L$.</p>

CC BY-SA 3.0
2018-04-18T22:06:15.000Z
So by "useful" I guess you mean significantly decreasing the resources required to solve the problem? e.g. nonuniform circuits that are significantly smaller than uniform ones, or turing machines with advice that run much faster than any without advice?
usul
CC BY-SA 3.0
2018-04-19T02:17:35.707Z
These are equivalent, no? I really meant useful as in "used to prove something interesting", though
Samuel Schlesinger
CC BY-SA 3.0
2018-04-19T02:19:00.080Z
I guess I'd imagine that all interesting things you'd prove using non-uniformity would basically fall into what you say, excepting that maybe the circuits will be better than known uniform ones, but not better than possible ones
Samuel Schlesinger
<circuit-complexity><advice-and-nonuniformity>
What are examples of how non-uniformity can be useful?
Samuel Schlesinger
# What are examples of how non-uniformity can be useful?

(Asked by: username_0 on 2018-04-18)

I'm curious about ways in which you have seen non-uniformity be useful in computation. One way is randomness, as in $BPP \subseteq P/poly$, and another is look-up tables which are used to show that all languages have non-uniform circuits.

In particular, I'm interested in ways that objects known to exist via the probabilistic method and other non-constructive (or not-constructive-enough) proof methods can be leveraged using non-uniformity. I'd prefer the examples to be natural, not contrived. To be clear, a circuit for a contrived problem could be something like: given some language $L \in P$, I create a polynomial size circuit by computing some really hard function $f(|x|)$ using my advice and asking whether $f(|x|)^{n/|f(|x|)|} \oplus x \in L$.

**Tags:** circuit-complexity, advice-and-nonuniformity

> **Comments:**
> **username_1**: So by "useful" I guess you mean significantly decreasing the resources required to solve the problem? e.g. nonuniform circuits that are significantly smaller than uniform ones, or turing machines with advice that run much faster than any without advice?  
> **username_0**: These are equivalent, no? I really meant useful as in "used to prove something interesting", though  
> **username_0**: I guess I'd imagine that all interesting things you'd prove using non-uniformity would basically fall into what you say, excepting that maybe the circuits will be better than known uniform ones, but not better than possible ones  

---

## 3 answers

### Answer by username_2 on 2018-04-18. Score: 11

An example I like is the argument that $\mathrm{NE\subseteq coNE}/(n+1)$ by counting strings in the language (see e.g. <https://blog.computationalcomplexity.org/2004/01/little-theorem.html>).

> **Comments:**
> **username_0**: This is great, because it doesn't rely on the probabilistic method or look-up tables. Thanks for this.  
> **username_0**: I think advice classes are usually not defined to have exact advice length @RickyDemer  
> **username_0**: Also, I can't see this in my attempts so far, so if someone could give a reference or mention how to see it, I'd appreciate it  
> **username_2**: All right, so $2^n+1$ possible values make about $n+2^{-n}\le n+1$ bits.  
> **username_3**: @SamuelSchlesinger: While P/poly or C/log (for any class C) are usually defined with advice length up to big-Oh, that's not always true. Some results use an exact number of advice bits (sometimes as small as 1!).  
> **username_0**: @JoshuaGrochow: right, thank you. I saw that recently while reading some of the work using the easy witness method in the early 2000s actually.  

---

### Answer by username_4 on 2018-04-18. Score: 10

One example is $\mathbf{NL} \subseteq \mathbf{UL}/\text{poly}$. This theorem was proven by Reinhardt and Allender in their paper ["Making Nondeterminism Unambiguous"](http://ftp.cs.rutgers.edu/pub/allender/nlul.pdf). Without going into the details, the advice in their algorithm consists of a sequence of edge-weight assignments so that for any digraph $G$ encoded by an $n$-bit string, some assignment in the sequence makes $G$ "min-unique". Such a sequence can be shown to exist by the probabilistic method. Reinhardt and Allender's main contribution was to give unambiguous log-space algorithms for figuring out *which assignment* in the sequence works for a particular given digraph $G$ and for deciding $s$-$t$ connectivity on a min-unique digraph.

As with $\mathbf{BPP} \subseteq \mathbf{P}/\text{poly}$, it is conjectured that nonuniformity is not actually necessary here, i.e., it is conjectured that $\mathbf{NL} = \mathbf{UL}$.


---

### Answer by username_5 on 2018-04-19. Score: 6

I am not sure if it fits what you are looking for, but there are a few results proving hierarchy theorems for semantic complexity classes with one bit of advice, where no hierarchy theorem is known without advice. The best known example is BPP, for which we do not know a hierarchy theorem, but Fortnow and Santhanam showed one exists with one bit of advice (building on a result of Barak that used more advice). [This article](https://link.springer.com/article/10.1007/s00037-007-0227-8) by Melkebeek and Pervyshev gives references and the history, and a theorem that seems to subsume the previous ones.

> **Comments:**
> **username_6**: If it is only one bit can't we just cycle through it like it case of $P/log$?  
> **username_5**: @username_6 Is your claim that BPP/1 is the same as BPP. Try to write down a proof and you should be able to easily see for yourself where this goes wrong  

---

