Fixed-Polynomial Size Circuit Bounds

Lance Fortnow, Rahul Santhanam

Research output: Contribution to journalArticlepeer-review

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).
Original languageEnglish
Number of pages11
JournalElectronic Colloquium on Computational Complexity (ECCC)
Volume13
Issue number157
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'Fixed-Polynomial Size Circuit Bounds'. Together they form a unique fingerprint.

Cite this