Name
Abstract | ||
|---|---|---|
We present several characterizations of the class PSPACE /poly. These characterizations are given in terms of PSPACE -complete problems, certain algebraic closure operations, vectorial straight-line programs, and Kolmogorov complexity. To end, we characterize the problems having an exponential lower bound on their nonuniform complexity measured by vectorial straight-line programs. |
Year | DOI | Venue |
|---|---|---|
1987 | 10.1016/0304-3975(87)90111-3 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
class pspace | Journal | 52 |
Issue | ISSN | Citations |
3 | Theoretical Computer Science | 5 |
PageRank | References | Authors |
0.65 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. L. Balcázar | 1 | 58 | 4.24 |
| Josep Díaz | 2 | 65 | 7.03 |
| J. Gabarró | 3 | 70 | 6.54 |