Questions tagged [circuits]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
12
votes
1answer
489 views

Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?

I was reading a paper of Buhrman and Homer “Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy”. On the bottom of page 2 they remark that the results of Kannan imply that $...
4
votes
2answers
466 views

P/poly vs NP separation based on circuit trees instead of DAGs

there are various theorems that relate major complexity class separations to circuit family DAGs sizes, in particular for P/poly vs NP. in contrast, are there theorems/conjectures that relate P/...