13
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 ...
- 18.6k
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).
- 18.6k
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, ...
- 1,763
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-...
- 1,763
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 ...
- 18.6k
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 ...
- 1,763
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 ...
- 18.3k
5
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 $...
- 121
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 ...
- 12.4k
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,675
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.6k
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,763
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 ...
- 1,234
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 ...
- 2,194
Only top scored, non community-wiki answers of a minimum length are eligible