Author name cluster

Birgit Jenner

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

I&C Journal 1996 Journal Article

Logspace and Logtime Leaf Languages

Birgit Jenner
Pierre McKenzie
Denis Thérien

The computation tree of a nondeterministic machineMwith inputxgives rise to aleaf stringformed by concatenating the outcomes of all the computations in the tree in lexicographical order. We may characterize problems by considering, for a particular “leaf language”Y, the set of allxfor which the leaf string ofMis contained inY. In this way, in the context of polynomial time computation, leaf languages were shown to capture many complexity classes. In this paper, we study the expressibility of the leaf language mechanism in the contexts of logarithmic space and of logarithmic time computation. We show that logspace leaf languages yield a much finer classification scheme for complexity classes than polynomial time leaf languages, capturing also many classes withinP. In contrast, logtime leaf languages basically behave like logtime reducibilities. Both cases are more subtle to handle than the polynomial time case. We also raise the issue of balanced versus nonbalanced computation trees underlying the leaf language. We indicate that it is a nontrivial problem to obtain information about the leaf string of a nonbalanced computation tree and present conditions under which it does not matter whether the computation tree is balanced or not.

Details DOI

TCS Journal 1995 Journal Article

Computing functions with parallel queries to NP

Birgit Jenner
Jacobo Torán

The class Θ 2 p of languages polynomial-time truth-table reducible to sets in NP has a wide range of different characterizations. We consider several functional versions of Θ 2 p based on these characterizations. We show that in this way the three function classes FLlog NP, FPlog NP, and FP∥ NP are obtained. In contrast to the language case the function classes seem to all be different. We give evidence in support of this fact by showing that FLlog NP coincides with any of the other classes then L = P, and that the equality of the classes FPlog NP and FP∥ NP would imply that the number of nondeterministic bits needed for the computation of any problem in NP can be reduced by a polylogarithmic factor, and that the problem can be computed deterministically with a subexponential time bound of order 2 n O(1/log log n).

Details DOI

TCS Journal 1995 Journal Article

On adaptive DLOGTIME and POLYLOGTIME reductions

Carme Àlvarez
Birgit Jenner

We investigate properties of the relativized AC and NC hierarchies in their DLOGTIME-, respectively, ALOGTIME-uniform setting and show that these hierarchies can be characterized in terms of adaptive reducibility in deterministic (poly)logarithmic time, i. e. in time O(log n) i for i ⩾ 0. Using this characterization, we substantially generalize various previous results concerning the structure of the two hierarchies.

Details DOI

TCS Journal 1993 Journal Article

A very hard log-space counting class

Carme Álvarez
Birgit Jenner

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 NC2, 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.

Details DOI

I&C Journal 1989 Journal Article

The logarithmic alternation hierarchy collapses: AΣ2L = AΠ2L

Birgit Jenner
Bernd Kirsig
Klaus-Jörn Lange

We show that AΣ 2 L = AΣ k L, k ≥ 2, by proving that AΣ 2 L coincides with AΠ 2 L. Essentially this is done by reducing the AΣ 2 L -complete set (GAP¢CoGap)(ℶ) to the question whether of two vectors A and B of n components, A contains more “solvable” components, i. e. , components which are contained in GAP, than B. Moreover, using a similar technique we show AΣ 2 L = Lhd(NL). Finally, we consider the relevance of our proof technique for polynomial time classes, e. g. , the Boolean NP-Hierarchy.

Details DOI