Name
Abstract | ||
|---|---|---|
Consideration is given to the logarithmic space counting classes polynomial-time counterparts. Complete functions are obtained for these three classes in terms of graphs and finite automata. It is shown that surprisingly, span-L seems to be much harder counting class than #L and opt-L. It is demonstrated that span-L-functions can be computed in polynomial time if and only if P=NP=PH=P(#P), i.e if the class P(#P) and all the classes of the polynomial-time hierarchy are contained 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 a subtraction of two functions in span-L. Nevertheless, #P⊆ span-L would imply NL=P=NP. An investigation is also conducted of various restrictions of the classes opt-L and span-L, and it is shown, e.g that if opt-L coincides with one of its restricted versions, then L=NL follows |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1109/SCT.1990.113964 | Barcelona |
Keywords | DocType | Citations |
computational complexity,finite automata,graph theory,#L,complexity theory,finite automata,graphs,opt-L,polynomial-time,span-L,very hard log space counting class | Conference | 34 |
PageRank | References | Authors |
1.42 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carme Àlvarez | 1 | 316 | 28.75 |
| Birgit Jenner | 2 | 247 | 14.47 |