All Questions
Tagged with succinct cc.complexity-theory
9 questions
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
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
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
6
votes
1
answer
569
views
On succinct $EXP$ and $NEXP$ complete problems?
We know succinct version of many $P$-complete problems are $EXP$-complete. There are standard ways to define $EXP$-complete graph problems from succinct representations of these $P$ complete problems. ...
- 13.3k
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
21
votes
3
answers
1k
views
Using Kolmogorov complexity as input "size"
Say we have a computational problem, e.g. 3-SAT, that has a set of problem instances (possible inputs) $S$.
Normally in the analysis of algorithms or computational complexity theory, we have some ...
- 284
3
votes
1
answer
289
views
Succinct Representation and Communication complexity
Succinct representation is often used to define NEXP or EXP complete problems. For example, when a graph is given as a circuit to compute the existence of edge between vertex $i,j$ for indices of $i,j$...
- 39
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
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