A reducibility concept for problems defined in ter

Authors: Ch Meinel A Slobodová

Publish Date: 2007/07/30

Volume: 30, Issue: 5, Pages: 495-518

PDF Link

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 subroutineHere 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 OBDDbased complexity classes it allows the reduction of problems to others which are computable with the same amount of OBDDresources and it gives a tool to carry over lower and upper bounds

Keywords: