Title :
Closure properties of GapP and #P
Author_Institution :
Dept. of Comput. Sci., Yale Univ., New Haven, CT, USA
Abstract :
We classify the relativizable closure properties of GapP, solving a problem posed by (Hertrampf et al., 1995). We also give a simple proof of their classification of functions that are relativizable closure properties of #P
Keywords :
Turing machines; computational complexity; GapP; closure properties; complexity; function classification; nondeterministic polynomial-time bounded Turing machine; problem solving; Artificial intelligence; Computer science; NASA; Polynomials; Radiofrequency interference; Terminology;
Conference_Titel :
Theory of Computing and Systems, 1997., Proceedings of the Fifth Israeli Symposium on
Conference_Location :
Ramat-Gan
Print_ISBN :
0-8186-8037-7
DOI :
10.1109/ISTCS.1997.595166
