4
$\begingroup$

Succinct version of permanent is $NEXP$-hard (https://eccc.weizmann.ac.il/report/2012/086/) and so unlikely to be $EXP$-complete.

Permanent mod $2$ is in $\oplus L$ and so succinct version is unlikely to be $EXP$-complete.

Is there a natural problem related to permanent that is $EXP$-complete?

$\endgroup$

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.