All Questions
Tagged with succinct cc.complexity-theory
6 questions with no upvoted or accepted answers
47
votes
0
answers
1k
views
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice ...
- 3,722
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
9
votes
0
answers
199
views
Is there a counting complexity class for succint problems?
Encoding NP-complete problems succintly often makes them NEXP-complete. I am wondering if counting the number of solutions to such a problem with a succint encoding would be any harder than solving ...
- 813
5
votes
0
answers
143
views
Succinct graphs with ability to perform random walk
Suppose I have an exponentially large graph $G$ ($|G|=2^n$) supplied with an efficient (of size $poly(n)$) randomized circuit $C_G$ implementing the random walk on $G$ - that is, $C_G$ takes a vertex ...
- 2,806
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
1
vote
0
answers
73
views
Is there a succinct representation of factoring which remains computationally intractable?
I'm looking for a succinct version of the factoring problem: i.e. given integers N and k, does N have a prime factor less than k, but somehow the input takes exponentially fewer bits to input? Ideally ...
- 403