Abstract:
Reducibility concepts are fundamental in complexity theory. Usually, they are defined as follows: A problem P is reducible to a problem S if P can be computed using a program or device for S as a subroutine. However, this approach has its limitations if restricted computational models are considered. In the case of ordered binary decision diagrams (OBDDs), it allows merely to use the almost unmodified original program for the subroutine. Here we propose a new reducibility concept for OBDDs: We say that P is reducible to S if an OBDD for P can be constructed by applying a sequence of elementary operations to an OBDD for S. In contrast to traditional reducibility notions, the newly introduced reduction is able to reflect the real needs of a reducibility concept in the context of OBDD-based complexity classes: it allows to reduce those problems to each other which are computable with the same amount of OBDD-resources and it gives a tool to carry over lower and upper bounds.

Abstract:
Reducibility concepts are fundamental in complexity theory. Usually, they are defined as follows: A problem P is reducible to a problem S if P can be computed using a program or device for S as a subroutine. However, in the case of such restricted models as ordered binary decision diagrams (OBDDs), this ap- proach is very limited in its power and leads necessarily to concepts which are quite meaningless for complexity theoretic considerations. In the paper, we propose a new reducibility concept for OBDDs. We say that P is reducible to S if an OBDD for P can be constructed by applying a sequence of computationally elemen- tary operations to an OBDD for S instead of using the unmodi- fied OBDD for S as a subroutine. Hence, P is reducible to S means that it is somewhat clear how to obtain a program for P from a program for S without insisting on an almost unmodified use of the original program. Although well-motivated, defining reducibility in terms of sequences of elementary operations has the disadvantage that it is very difficult to handle dynamically changing struc- tures. The main purpose of this paper is to establish an algo- rithmically based static description of this dynamical reduci- bility notion which makes adequate complexity theoretic inves- tigations possible.