Name
Abstract | ||
|---|---|---|
We introduce a new class of functions, called span functions which count the different output values that occur at the leaves of the computation tree associated with a nondeterministic polynomial time Turing machine transducer. This function class has natural complete problems; it is placed between Valiant's function classes #P and #NP, and contains both Goldberg and Sipser's ranking functions for sets in NP, and Krentel's optimization functions. We show that it is unlikely that the span functions coincide with any of the mentioned function classes. |
Year | DOI | Venue |
|---|---|---|
1988 | 10.1007/BFb0026095 | Acta Informatica |
Keywords | DocType | Volume |
Approximation Method,Computational Mathematic,Computer System,System Organization,Polynomial Time | Conference | 26 |
Issue | ISSN | ISBN |
4 | 0001-5903 | 3-540-19021-X |
Citations | PageRank | References |
25 | 5.05 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johannes Köbler | 1 | 31 | 6.83 |
| Uwe Schöning | 2 | 107 | 18.86 |
| Jacobo Torán | 3 | 26 | 5.68 |