Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COMPUTIONAL COMPLEXITY:
Reports tagged with computional complexity:
TR04-037 | 14th April 2004
Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner

Generation Problems

Given a fixed computable binary operation f, we study the complexity of the following generation problem: The input consists of strings a1,...,an,b. The question is whether b is in the closure of {a1,...,an} under operation f.

For several subclasses of operations we prove tight upper and lower bounds for the ... more >>>




ISSN 1433-8092 | Imprint