The definition of PPAD (Polynomial parity arguments on directed graphs) revolves around the definition of "End-Of-The-Line"

An exponentially large polynomial-depth arithmetic circuit, $f$, specifies a graph where every node has an in-degree and out-degree of at most $1$. Given that $0$'s in-degree doesn't match it's out-degree, find another node where the in-degree isn't equal to its out-degree

I don't understand why we can't just sub in arithmetic circuits with boolean circuits here.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.