TransWikia.com

Time complexity of Succinct-CVP

Theoretical Computer Science Asked by Mohsen Ghorbani on October 30, 2021

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP