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

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

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


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


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


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

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

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


2

How about foundations of disjunctive logic programming? While rather old (1992), it has over 100 examples. For instance, SLI and SLD resolutions are discussed and exemplified in section 4.2. PS: You may read some parts of that section on Google Books.


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