0
$\begingroup$

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.

$\endgroup$

0

Your Answer

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

Browse other questions tagged or ask your own question.