Revision #1 Authors: Christoph Meinel, Anna Slobodova

Accepted on: 22nd October 1996 00:00

Downloads: 1989

Keywords:

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.

TR96-010 Authors: Christoph Meinel, Anna Slobodova

Publication: 9th February 1996 13:35

Downloads: 2042

Keywords:

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.