2
$\begingroup$

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)$.

Improve this question
$\endgroup$
5
  • 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$
    – Bartosz Bednarczyk
    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$
    – Mohsen Ghorbani
    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$
    – Bartosz Bednarczyk
    Jul 18, 2020 at 14:28
  • $\begingroup$ @BartoszBednarczyk $1.4^n$ is good and $2^{n/(\log^5 n)}$ is great. $\endgroup$
    – Mohsen Ghorbani
    Jul 19, 2020 at 4:34
  • 2
    $\begingroup$ So please update your question accordingly. $\endgroup$
    – Bartosz Bednarczyk
    Jul 20, 2020 at 7:32

0

Reset to default

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.