I want to know what is the best known lower time complexity of Succinct-CVP? The succinct version of many P-complete problems are EXP-complete and Succinct-CVP is EXP-complete too (It is because of the local reductions). If we expand the circuit then we have an $2^n$ size CVP which is decidable in time $2^n$. I searched a lot to find a better algorithm for this problem I was looking for $2^{n/{\log^5 n}}$ time algorithm but I can't even find an algorithm with time complexity of $2^{n/3}$. So I want to know is there any research around this problem or a better algorithm?

Succinct-CVP: given a circuit $D(y_1,y_2,...,y_n)$ that is a succinct description of a circuit $C(x_1,x_2,...,x_n)$ of size at most $2^n$ and an input $a \in \{0,1\}^n$, Compute the value $C(a)$.

  • 3
    $\begingroup$ Should be Exp-complete. I found some notes here but you might need to search a bit to find the reference: users.cs.duke.edu/~reif/courses/complectures/Umans/lec2c.pdf $\endgroup$ Commented Jul 18, 2020 at 9:40
  • $\begingroup$ @BartoszBednarczyk Thank you. I know there is an $O(2^n)$ time algorithm for the problem but I think there should be better algorithms. I want to find an optimized algorithm. $\endgroup$ Commented Jul 18, 2020 at 10:00
  • $\begingroup$ But you were asking about the lower bound. What exactly is your question? Are you asking e.g. if you need (1,425285712)^n steps to solve the problem? $\endgroup$ Commented Jul 18, 2020 at 14:28
  • $\begingroup$ @BartoszBednarczyk $1.4^n$ is good and $2^{n/(\log^5 n)}$ is great. $\endgroup$ Commented Jul 19, 2020 at 4:34
  • 2
    $\begingroup$ So please update your question accordingly. $\endgroup$ Commented Jul 20, 2020 at 7:32


Your Answer

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