Name
Abstract | ||
|---|---|---|
We show that the class AM∩coAM is low for ZPPNP. As a consequence, it follows that Graph Isomorphism and several group-theoretic problems are low for ZPPNP. We also show that the class IP[P/poly], consisting of sets that have interactive proof systems with honest provers in P/poly, is also low for ZPPNP. For the nonuniform function classes NPMV/poly, NPSV/poly, and NPMVt/poly, we show the following lowness results: Sets whose characteristic functions are in NPSV/poly and that have program checkers are low for AM and ZPPNP. Self-reducible sets with characteristic functions in NPMVt/poly are low for Σ2p. Sets whose characteristic functions are in NPMV/poly and that have program checkers are low for Σ2p. We also give applications of these lowness results. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1006/jcss.2002.1835 | Journal of Computer and System Sciences |
Keywords | Field | DocType |
lowness,self-reducible set,interactive proof system,probabilistic class,function class,program checker. | Complexity class,Discrete mathematics,Combinatorics,Graph isomorphism,Interactive proof system,Characteristic function (probability theory),Mathematics | Journal |
Volume | Issue | ISSN |
65 | 2 | 0022-0000 |
Citations | PageRank | References |
2 | 0.37 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 122 | 12.03 |
| Johannes Köbler | 2 | 580 | 46.51 |