A Note on SpanP Functions

Meena Mahajan, Thomas Thierauf, and Vinodchandran N.V.

Abstract:
Valiant introduced the class #P to count the number of solutions of NP sets. Recently, Fenner, Fortnow, and Kurtz considered the class GapP, the closure of #P under subtraction, and showed many interesting properties of this class. Koebler, Schoening, and Toran introduced the class SpanP that counts the number of distinct outputs produced by a nondeterministic Turing machine. With this concept, they could distinguish between whether two given graphs are isomorphic or not. We introduce the class GapSpanP, the closure of SpanP under subtraction. We show that this class of functions coincides with the class GapP^NP.