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:
...
- 1,310
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 ...
- 632
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 ...
- 16.8k
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 ...
- 1,757
Only top scored, non community-wiki answers of a minimum length are eligible