Mahajan, Meena ; Thierauf, Thomas ; Vinodchandran, N.V. (1994) A note on SpanP functions Information Processing Letters, 51 (1). pp. 7-10. ISSN 0020-0190
Full text not available from this repository.
Official URL: http://doi.org/10.1016/0020-0190(94)00068-9
Related URL: http://dx.doi.org/10.1016/0020-0190(94)00068-9
Abstract
Valiant 10] introduced the class# P to count the number of solutions of NP sets. Recently, Fenner, Fortnow, and Kurtz 3] considered the class GapP, the closure of# P under subtraction, and showed many interesting properties of this class. K obler, Sch oning, and Tor an 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 GapPNP.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier B.V. |
| Keywords: | Computational complexity |
| ID Code: | 128020 |
| Deposited On: | 14 Oct 2022 11:27 |
| Last Modified: | 14 Oct 2022 11:27 |
Repository Staff Only: item control page
