Skip to main content
11 votes

What are examples of how non-uniformity can be useful?

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).
Emil Jeřábek's user avatar
10 votes

What are examples of how non-uniformity can be useful?

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, ...
William Hoza's user avatar
  • 1,733
9 votes

P/Poly vs Uniform Complexity Classes

$\let\mr\mathrm$There are several results in the literature stating that a certain class $C$ satisfies $C\nsubseteq\mr{SIZE}(n^k)$ for any $k$, and usually it is straightforward to pad them to show ...
Emil Jeřábek's user avatar
9 votes
Accepted

What are the consequences of $P \subseteq L/poly$?

One simple consequence is $\mathbf{P}/\text{poly} = \mathbf{L}/\text{poly}$. Proof: For any language $A \in \mathbf{P}/\text{poly}$, there is a language $B \in \mathbf{P}$ and a sequence of polynomial-...
William Hoza's user avatar
  • 1,733
8 votes
Accepted

Is there a well-defined notion of an “R/poly” complexity class?

There is nothing stopping you from defining the class, though I don’t recall seeing it studied. Actually, I can see two reasonable definitions for this class. The first one, which follows more ...
Emil Jeřábek's user avatar
7 votes
Accepted

Does the space hierarchy theorem generalize to non-uniform computation?

One non-uniform "space hierarchy" that we can prove is a size hierarchy for branching programs. For a Boolean function $f: \{0, 1\}^n \to \{0, 1\}$, let $B(f)$ denote the smallest size of a branching ...
William Hoza's user avatar
  • 1,733
6 votes

What are examples of how non-uniformity can be useful?

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 ...
Sasho Nikolov's user avatar
4 votes
Accepted

When is a problem specified on a TM contained in non-uniform classes such as P/poly?

If $N$ were written in unary, then the language would be a unary language, i.e., a subset of $\{0,1\}^*$. Every unary language is in P/poly. That's because a P/poly machine is allowed a separate ...
D.W.'s user avatar
  • 12.1k
4 votes

P/Poly vs Uniform Complexity Classes

Please correct me if I'm wrong, but as far as I can tell, we actually don't know a fixed-polynomial size lower bound for $O_2^P$. This is because the usual Karp-Lipton argument doesn't go through for $...
Apoorva Bhagwat's user avatar
4 votes
Accepted

P/Poly vs Uniform Complexity Classes

Since nobody posted an answer, I will answer the question myself with the comments posted in the original question. Thanks to Robin Kothari, Emil Jerabek, Andrew Morgan and Alex Golovnev. $MA_{exp}$ ...
Springberg's user avatar
3 votes
Accepted

What do stronger circuit lower bounds give in terms of derandomization?

It is known that if $E = DTIME(2^{O(n)})$ is not contained in $SIZE(2^{\varepsilon \cdot n})$ for some $\varepsilon>0$ then $BPP = P$ (https://dl.acm.org/citation.cfm?id=258590). (Actually, a ...
Or Meir's user avatar
  • 5,460
3 votes

Non-Uniform Lower Bounds for NSPACE

For any space-constructible function $f$ such that $f(n)=\omega(n)$, we have $\mathrm{NSPACE}(f(n)\log n)\nsubseteq\mathrm{SIZE}(n)$. This follows by simple brute force: you can compute the predicate ...
Emil Jeřábek's user avatar
3 votes

Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$?

Nothing better than $\mathbf{BPP}/\text{poly} = \mathbf{P}/\text{poly}$ is known. On the other hand, better results are known in the space bounded setting. Fortnow and Klivans showed that $\mathbf{BPL}...
William Hoza's user avatar
  • 1,733
2 votes

NC0 randomnes vs. non-uniformity

Any $NC^0$ circuit family $(C_n)_{n \geq 0}$ can only depend on a constant number of bits, whether they're input bits or random bits. Let's say there are $n$ inputs and $r$ random bits, but our ...
Jake's user avatar
  • 1,214
2 votes

When is a problem specified on a TM contained in non-uniform classes such as P/poly?

It is always difficult to answer the question why did the authors phrase this in such and such a way, so I can only guess. My guess is that they assume certain background knowledge, which I now lay ...
Lieuwe Vinkhuijzen's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible