<p>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 <span class="math-container">$2^n$</span> size CVP which
is decidable in time <span class="math-container">$2^n$</span>. I searched a lot to find a better algorithm for this problem I was looking for <span class="math-container">$2^{n/{\log^5 n}}$</span> time algorithm but I can't even find an algorithm with time complexity of <span class="math-container">$2^{n/3}$</span>. So I want to know is there any research around this problem or a better algorithm?</p>
<p><strong>Succinct-CVP</strong>: given a circuit <span class="math-container">$D(y_1,y_2,...,y_n)$</span> that is a succinct description of a circuit <span class="math-container">$C(x_1,x_2,...,x_n)$</span> of size at most <span class="math-container">$2^n$</span> and an input <span class="math-container">$a \in \{0,1\}^n$</span>, Compute the value <span class="math-container">$C(a)$</span>.</p>

CC BY-SA 4.0
2020-07-18T09:40:38.747Z
Should be Exp-complete. I found some notes here but you might need to search a bit to find the reference: https://users.cs.duke.edu/~reif/courses/complectures/Umans/lec2c.pdf
Bartosz Bednarczyk
CC BY-SA 4.0
2020-07-18T10:00:20.973Z
@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.
Mohsen Ghorbani
CC BY-SA 4.0
2020-07-18T14:28:21.917Z
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?
Bartosz Bednarczyk
CC BY-SA 4.0
2020-07-19T04:34:25.563Z
@BartoszBednarczyk $1.4^n$ is good and $2^{n/(\log^5 n)}$ is great.
Mohsen Ghorbani
CC BY-SA 4.0
2020-07-20T07:32:20.393Z
So please update your question accordingly.
Bartosz Bednarczyk
<time-complexity><lower-bounds><exp-time-algorithms><succinct>
Time complexity of Succinct-CVP
Mohsen Ghorbani
# Time complexity of Succinct-CVP

(Asked by: username_0 on 2020-07-18)

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

**Tags:** time-complexity, lower-bounds, exp-time-algorithms, succinct

> **Comments:**
> **username_1**: Should be Exp-complete. I found some notes here but you might need to search a bit to find the reference: https://users.cs.duke.edu/~reif/courses/complectures/Umans/lec2c.pdf  
> **username_0**: @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.  
> **username_1**: 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?  
> **username_0**: @BartoszBednarczyk $1.4^n$ is good and $2^{n/(\log^5 n)}$ is great.  
> **username_1**: So please update your question accordingly.  

---

## 0 answers

