Name
Abstract | ||
|---|---|---|
We show that computing iterated multiplication of word matrices over {0,1}*, using the operations maximum and concatenation, is complete for the class optL of logspace optimization functions. The same problem for word matrices over {1}* is complete for the class FNL of nondeterministic logspace functions. Improving previously obtained results, we furthermore place the class optL in AC1, and characterize FNL by restricted logspace optimization functions. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1007/BF01268143 | Computational Complexity |
Keywords | DocType | Volume |
complexity classes,optimiza- tion,nondeterministic logspace,iterated multiplication.,logspace optimization,complexity class,optimization | Journal | 5 |
Issue | ISSN | Citations |
2 | 1420-8954 | 2 |
PageRank | References | Authors |
0.36 | 10 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carme Àlvarez | 1 | 316 | 28.75 |
| Birgit Jenner | 2 | 247 | 14.47 |