# Tag Info

18

Here is a possible alternative to a padding argument, based on Schöning's generalization of Ladner's theorem. To understand the argument, you need to have access to this paper (which will unfortunately be behind a pay wall for many): Uwe Schöning. A uniform approach to obtain diagonal sets in complexity classes. Theoretical Computer Science 18(1):95-103,...

15

I'd just like to write down some version of a padding argument as described in the comments. I don't see why a gap is needed. We want to show that if NP is not contained in P/poly then there is an NP-intermediate problem not contained in P/poly. There is an unbounded function $f$ such that SAT does not have circuits of size less than $n^{f(n)}$, and so ...

11

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

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

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

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

Using a pairing function we can allow $s$ to be defined on $\mathbb{N}^2$. Let $s(i,j)=1$ if and only if the $i$'th program $P_i$ halts in at most $2^j$ steps. Then $V$ can test whether $P_i$ halts by testing $s(i,1),s(i,2),\dots$. If $U(P_i)$ halts in at most $2^j$ steps then $V(P_i)$ halts in about $(i+j)^2$ time, assuming the pairing function is sensible. ...

4

The question was answered by Emil Jerabek at https://mathoverflow.net/questions/115275/non-uniform-complexity-of-the-halting-problem

4

Just an extended comment: I'm not an expert, but for what regards 1., something can be said if you interpret: $HALT(k) = 1$ iif $TM_k$ halts on the empty tape. In this case the string $s$ that lists the first $n$ bits $HALT(k)$, $k = 1,2,...,n$ is highly compressible: $|s|=n$ let $h$ be the number of halting TMs between $1$ and $n$ ($h \leq n$) If you ...

4

Perhaps you'd be interested in switching networks. According to Potechin's Bounds on monotone switching networks for directed connectivity, one way to separate L from NL is to show that there is no polysize switching network for directed connectivity. There is in fact a (trivial) polysize switching-and-rectifier network for directed connectivity. The ...

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

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

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.

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