Name
Abstract | ||
|---|---|---|
We consider the logarithmic-space counting and optimization classes #L, span-L, and opt-L, which are defined analogously to their polynomial-time counterparts. We obtain complete functions for these three classes in terms of graphs and finite automata. We show that #L and opt-L are both included in NC 2 , but that, surprisingly, span-L seems to be a much harder class than #L and opt-L. We demonstrate that span-L functions can be computed in polynomial time if and only if P (#P) and all the classes of the polynomial-time hierarchy are included in P. This result follows from the fact that span-L and #P are very similar: span-L ⊆ #P, and any function in #P can be represented as the difference of a function in FL and a function in span-L. Nevertheless, the inclusion #P ⊆ span-L would imply NL = P = NP . We, furthermore, investigate restrictions of the classes opt-L and span-L. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1016/0304-3975(93)90252-O | Theor. Comput. Sci. |
Keywords | Field | DocType |
hard log-space,polynomials,ducts,turing machines,l,graphs,graph theory,polynomial time,finite automata,automata,np complete problem,computational complexity | Graph theory,Discrete mathematics,Combinatorics,Polynomial,P,K-independent hashing,Perfect hash function,Hash function,Time complexity,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
107 | 1 | Theoretical Computer Science |
Citations | PageRank | References |
46 | 1.91 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carme Àlvarez | 1 | 316 | 28.75 |
| Birgit Jenner | 2 | 247 | 14.47 |