A reducibility concept for problems defined in terms of ordered binary decision diagrams |
| |
Authors: | Ch Meinel A Slobodová |
| |
Affiliation: | 1. FB IV-Informatik, Universit?t Trier, D-54286, Trier, Germany 2. ITWM-Trier, Bahnhofstrasse 30–32, D-54292, Trier, Germany
|
| |
Abstract: | Reducibility concepts are fundamental in complexity theory. Usually, they are defined as follows: A problem Π is reducible
to a problems Σ if Π can be computed using a program or device for Σ 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 the
use of merely the almost unmodified original program for the subroutine.
Here we propose a new reducibility for OBDDs: We say that Π is reducible to Σ if and OBDD for Π can be constructed by applying
a sequence of elementary operations to an OBDD for Σ. 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 the reduction of problems to others which are computable with the same amount of OBDD-resources and it gives a tool
to carry over lower and upper bounds.
The authors are grateful to DAAD Acciones Integradas, Grant No. 322-ai-e-dr. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|