期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
