This is a question from the lecture about Toda's theorem:


The lecture uses theorem 1 and theorem 2 but not include proof. My question is how to proof?

Theorem 2:

$L \in \oplus P$ iff $L$ can be computed by a DC uniform circuit $\{D_n\}$ that

use $AND$, $OR$, $NOT$, $XOR$ gates.

has size $2^{n^{O(1)}}$ and constant depth

$XOR$ gates can have unbounded (exponential) fanin, but $AND$, $OR$ gates have fanin at most $n^{O(1)}$

$NOT$ gates can appear anywhere in the circuit.

This question may not be a research level question, but I really want to know the answer. If someone can give me a detailed reference, I will appreciate that.


The circuit characterization are by Kannan, Venkateswaran, Vinay, and Yao given in the paper:

A Circuit-Based Proof of Toda′s Theorem

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.