9
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – usul
    Apr 18 '18 at 22:06
  • $\begingroup$ These are equivalent, no? I really meant useful as in "used to prove something interesting", though $\endgroup$
    – Samuel Schlesinger
    Apr 19 '18 at 2:17
  • $\begingroup$ 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 $\endgroup$
    – Samuel Schlesinger
    Apr 19 '18 at 2:19
11
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ This is great, because it doesn't rely on the probabilistic method or look-up tables. Thanks for this. $\endgroup$
    – Samuel Schlesinger
    Apr 19 '18 at 2:23
  • $\begingroup$ (Note that if the advice-string's length must be exact, then $n$ doesn't quite obviously work (and I don't see any way to show that it works, obvious-nor-not).) ​ ​ $\endgroup$
    – user6973
    Apr 19 '18 at 2:27
  • $\begingroup$ I think advice classes are usually not defined to have exact advice length @RickyDemer $\endgroup$
    – Samuel Schlesinger
    Apr 19 '18 at 2:45
  • $\begingroup$ 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 $\endgroup$
    – Samuel Schlesinger
    Apr 19 '18 at 2:47
  • 1
    $\begingroup$ @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!). $\endgroup$
    – Joshua Grochow
    May 1 '18 at 19:00
10
$\begingroup$

One example is $\mathbf{NL} \subseteq \mathbf{UL}/\text{poly}$. This theorem was proven by Reinhardt and Allender in their paper "Making Nondeterminism Unambiguous". 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}$.

Improve this answer
$\endgroup$
6
$\begingroup$

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 by Melkebeek and Pervyshev gives references and the history, and a theorem that seems to subsume the previous ones.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If it is only one bit can't we just cycle through it like it case of $P/log$? $\endgroup$
    – Mr.
    May 22 '18 at 18:02
  • $\begingroup$ @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 $\endgroup$
    – Sasho Nikolov
    Jun 3 '18 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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