5 votes
Accepted

Deciding finiteness of regular language is NL-complete?

Let $\mathcal{A}$ be an NFA. We say that a state $q$ lies on a cycle if there is a non-empty path from $q$ to $q$ in the graph of $\mathcal{A}$. In my answer I assume that the following lemma is true: ...
Bartosz Bednarczyk's user avatar
4 votes
Accepted

Intuition on Lupanov's Upper Bound on Circuit Size

Yes, there is a simpler construction, essentially due to Shannon. For every $k$, all $2^{2^k}$ functions on $k$ variables can implemented by a circuit of size $2^{2^k}$ (just take some implementation ...
Vladimir Lysikov's user avatar
3 votes

What can we do with a generic oracle (as opposed to a random one)?

Unless I am mistaken, GenericallyP = P: Proposition. The following are equivalent for any language $L$: $L\in\mathbf P$. $L\in\mathbf{GenericallyP}$. $\{A\in\{0,1\}^\mathbb N:L\in\mathbf P^A\}$ is ...
Emil Jeřábek's user avatar
2 votes

Is counting the union of power sets NP-complete?

It is $\#P$-complete. Here is a reduction from counting vertex covers. Let $G = (V,E)$. We wish to count the number of sets of vertices that are not vertex covers. We observe a set $X \subseteq V$ is ...
Laakeri's user avatar
  • 1,757

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