All Questions
2 questions
14
votes
0
answers
475
views
Is there a P-complete language X such that succinct-X is in P?
I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\...
- 5,167
4
votes
0
answers
112
views
A succinct version of permanent that is $EXP$-complete
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 ...
- 13.3k