Nonuniform catalytic space and the direct sum for space

摘要

This paper initiates the study of k -catalytic branching programs, a nonuniform model of computation that is the counterpart to the uniform catalytic space model of Buhrman, Cleve, Koucky, Loff and Speelman (STOC 2014). A k -catalytic branching program computes k boolean functions simultaneously on the same n -bit input. Each function has its own entry, accept and reject nodes in the branching program but internal nodes can otherwise be shared. The question of interest is to determine the conditions under which some form of a direct sum property for deterministic space can be shown to hold, or shown to fail.We exhibit both cases. There are functions that are correlated in such a way that their direct sum fails: a significant amount of space can be saved by sharing internal computation among the k functions. By contrast, direct sum is shown to hold in some special cases, such as for the family of functions ( l 1 ( l 2 ( ( l n ? 1 l n ) ) where each l i is a literal on variable x i , 1 i n and each stands individually for either or .