Abstract
We explore whether various complexity classes can have linear or more generally nk-sized circuit families for some fixed k. We show
1) The following are equivalent,
- NP is in SIZE(n^k) (has O(n^k)-size circuit families) for some k
- P^NP|| is in SIZE(n^k) for some k
- ONP/1 is in SIZE(n^k) for some k.
where ONP is the class of languages accepted by NP machines with some witness depending only on the input length.
2) For all k, MA is in SIZE(n^k) if and only if AM is in SIZE(n^k).
3) One cannot show Parity-P does not have
n^2-size circuit families without using nonrelativizing techniques
beyond those already used for similar results.
4) For every k, the class P^PP does not have n^k-sized circuits with Sigma_k^Parity-P-gates.
5) For a large number of natural classes C and constant k, C is in SIZE(n^k) if and only if C/1 \cap P/poly is in SIZE(n^k).
1) The following are equivalent,
- NP is in SIZE(n^k) (has O(n^k)-size circuit families) for some k
- P^NP|| is in SIZE(n^k) for some k
- ONP/1 is in SIZE(n^k) for some k.
where ONP is the class of languages accepted by NP machines with some witness depending only on the input length.
2) For all k, MA is in SIZE(n^k) if and only if AM is in SIZE(n^k).
3) One cannot show Parity-P does not have
n^2-size circuit families without using nonrelativizing techniques
beyond those already used for similar results.
4) For every k, the class P^PP does not have n^k-sized circuits with Sigma_k^Parity-P-gates.
5) For a large number of natural classes C and constant k, C is in SIZE(n^k) if and only if C/1 \cap P/poly is in SIZE(n^k).
Original language | English |
---|---|
Number of pages | 11 |
Journal | Electronic Colloquium on Computational Complexity (ECCC) |
Volume | 13 |
Issue number | 157 |
Publication status | Published - 2006 |