People who code: we want your input. Take the Survey

# Tag Info

12

Emil Jeřábek' comment answers the question: P/poly $=$ NP/poly is equivalent to NP $\subseteq$ P/poly Note the corollary P/poly $\neq$ NP/poly implies P $\neq$ NP. Proof of corollary: P/poly $=$ NP/poly is equivalent to NP $\subseteq$ P/poly $\$ (Emil's comment) NP $\subseteq$ P/poly implies P/poly $=$ NP/poly $\$ (implied by 1.) P/poly $\neq$ NP/...

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

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

9

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-length advice strings $y_1, y_2, y_3, \dots$ such that $x \in A \iff (x, y_{|x|}) \in B$. By assumption, there is a language $C \in \mathbf{L}$ and a sequence ...

9

$\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 that any barely superpolynomially expanded version of $C$ is not in $\mr{P/poly}$. Let me say that $f\colon\mathbb N\to\mathbb N$ is a superpolynomial bound if ...

7

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 program computing $f$. By an argument analogous to this hierarchy argument for circuit size, one can show that there are constants $\epsilon, c$ so for every ...

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

4

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 advice string, one per length of the input. The advice string for length $n$ could just describe whether the input $1^n$ should be accepted or not. Or, to put ...

4

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 $O_2^P$, since we don't know whether $\textsf{NP}\subseteq O_2^P$ (in fact, this is equivalent to asking whether $\textsf{NP}\subseteq \textsf{P/poly}$). ...

4

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}$ seems to be the smallest uniform class with known superpolynomial lower bounds. $O_2^P$ seems to be the smallest known class not having circuits of size $n^k$...

3

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 slightly stronger assumption is needed, namely, the separation between $E$ and $SIZE(2^{\varepsilon \cdot n})$ should hold for almost all input lengths - thanks to ...

3

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 $\exists$ a truth-table $t$ of a Boolean function in $O(\log f(n))$ variables such that ($\forall$ circuit $C$ of size $f(n)$, $C$ does not compute $t$) and (...

3

Yes. All advice strings of length log n can be cycled though in polynomial time. The polynomial time algorithm for SAT would be: For each of the polynomially many advice strings, try to use it to produce a satisfying assignment for SAT (using self-reducibility) in polynomial time. I would guess this is in the original Karp Lipton paper.

3

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} \subseteq \mathbf{L}/O(n)$ (see this paper for a refinement). It follows that $\mathbf{BPL}/O(n) = \mathbf{L}/O(n)$.

2

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 out. The only input to the problem in the paper is $N$, which is given in binary, because, as the authors mention If instead we were given $N$ in unary, there ...

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