A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

14 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
453 views

### What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?

Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows. Is there a result comparable to the Karp-...
334 views

246 views

### Is Solomonoff Induction in $\mathsf{P/poly}$?

Consider any language $L$. Define $s(L) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula $$s(L)_n=\chi_L(s(L)_{<n})$$ Here $\chi_L$ is the characteristic ...
196 views

### Non-uniform average-case complexity of NP

It is conjectured that NP-complete problems are hard not only in the worst case but also in the typical case. Formally, given a language $S \in \lbrace 0,1 \rbrace^*$ and for each $n$ a probability ...
290 views

### Oracle separating $coNP$ and $NP/poly$

I'd like to prove that, with respect to some adversarial oracle $O$, $coNP^O \not\subseteq NP/poly^O$. I was thinking of using $\textsf{UNSAT}$ for this and to build my oracle as follows: $O$ will "...
106 views

### What is the strongest known lower bound against SIZE(n)?

What is the best known lower bound against (nonuniform) circuits of size $O(n)$? I understand that we don't know of any explicit functions that need circuits of size more than something like $5n$. But ...
150 views

### Survey on the Power of Non-Uniformity

I know that BPP is in P/poly. I know that if NP is in P/poly then $PH = \Sigma^2_p$ Question: Is there a good survey on the power of non-uniformity? I'm basically looking for a list of known ...
112 views

$FP^{NP[O(n)]}$ is the functional complexity class with $O(n)$ queries to an $NP$ oracle. Are there any interesting classes $\mathcal C$ such that $$FP^{NP[O(n)]}\subseteq\mathcal C/\log$$ besides $... 0answers 109 views ### Conditional Results on Bounded Depth Circuit Hierarchy$\mathsf{AC,ACC,TC}$-hierarchy are basic bounded depth circuit hierarchies.$AC$-hierarchy is$\bigcup _{i =0}^{\infty} AC^{i} $, where$AC^{i}$is the$i$-th level of the hierarchy: a family of$\...
Is anything known about ExpSpace problems whose configuration reachability problems are in P/poly? Let $M$ be an ExpSpace machine. Given two configurations $a$ and $b$ of $M$ (of max length), ...