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:
...
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 ...
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 ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
cc.complexity-theory × 3018complexity-classes × 497
reference-request × 348
np-hardness × 337
ds.algorithms × 250
graph-theory × 238
circuit-complexity × 238
sat × 148
counting-complexity × 146
time-complexity × 145
graph-algorithms × 139
quantum-computing × 121
lower-bounds × 114
reductions × 93
big-picture × 81
lo.logic × 80
approximation-algorithms × 78
approximation-hardness × 76
np × 76
co.combinatorics × 74
boolean-functions × 74
computability × 69
optimization × 60
np-complete × 60
cr.crypto-security × 59