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.