# Tag Info

Accepted

### Can we approximate the number of words accepted by an NFA?

There exists a FPRAS (Fully Polynomial Randomized Approximation Scheme) for the problem of counting the words of length $n$ accepted by a NFA in the general case (without restricting to the acyclic ...
• 521
Accepted

• 3,236
Accepted

• 8,273
1 vote

### Complexity of optimal elimination for a planar tensor network

From Dumitrescu et al.: In 2005, Markov and Shi showed that optimal contraction sequences correspond to optimal (minimum width) tree decompositions of a tensor network's line graph. From Bryan O'...
1 vote

### Efficient and simple randomized algorithms where determinism is difficult

Finding a 2-approximate weighted vertex cover is known to be in RNC [1]. I don't think it is known to be in NC. That is, the problem has a randomized poly-log-time poly-processor algorithm, but I don'...
• 8,273

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