On Closure Properties of GapP

Thomas Thierauf, Seinosuke Toda, and Osamu Watanabe

Abstract:
We study the closure properties of the function classes GapP and GapP_+. We characterize the property of GapP_+ being closed under decrement and of GapP being closed under maximum, minimum, median, or division by seemingly implausible collapses among complexity classes; thereby giving evidence that these function classes don't have these closure properties.

We show a similar result concerning operations we call bit cancellation and bit insertion: Given a function f in GapP and a polynomial-time computable function k. Then we ask whether the function f^*(x) that is obtained from f(x) by canceling the k(x)th bit in the binary representation of f(x), or whether the function f^+(x) that is obtained from f(x) by inserting a bit at position k(x) in the binary representation of f(x), is also in GapP. We give necessary conditions and a sufficient conditions for GapP being closed under bit cancellation and bit insertion, respectively.