# Tag Info

### 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 ...
• 18.2k

### 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).
• 18.2k

### 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, ...
• 1,743
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-...
• 1,743
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 ...
• 18.2k
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 ...
• 1,743

### 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 ...
• 18.2k
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 ...
• 12.3k

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 $... 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}$... • 686 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 ... • 5,625 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 ... • 18.2k 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}...
• 1,743
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 ...