Name
Abstract | ||
|---|---|---|
:We study the polynomial time counting hierarchy, a hierarchy of complexity classes relatedto the notion of counting. We investigate some of their structural properties, settling manyopen questions dealing with oracle characterizations, closure under boolean operations,and relations with other complexity classes. We develop a new combinatorial techniqueto obtain relativized separations for some of the studied classes, which imply absoluteseparations for some logarithmic time bounded... |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1145/116825.116858 | J. ACM |
Keywords | Field | DocType |
counting complexity classes,complexity class | Complexity class,Discrete mathematics,Computer science | Journal |
Volume | Issue | ISSN |
38 | 3 | 0004-5411 |
Citations | PageRank | References |
70 | 3.06 | 11 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jacobo Torán | 1 | 564 | 49.26 |