3 ms·
Something is up with the succinct circuits description. > An n-node simple graph can have up to 2^n edges, meaning it takes exponential space to encode An n-n
by klyrs 3y ago
Something is up with the succinct circuits description.
> An n-node simple graph can have up to 2^n edges, meaning it takes exponential space to encode
An n-node simple graph can only have O(n^2) edges, and only needs quadratic space to encode.
- deleted 3y ago[deleted]
- perihelions 3y agoPretty sure "n-node" is a typo and both vertices and edges are 2ⁿ.
- hwayne 3y agoNo, it's a dumb mistake, I was thinking of the number of subgraphs of the N-node graph. I'll fix it.
- klyrs 3y agoI'm not sure you want subgraphs, either. Succinct circuits encode exponential-sized graphs in poly space. I read a little on this, and I realize I've seen examples of succinct circuits. Hash functions are a great example of poly-sized circuits that compute the edges of exponentially-large graphs (fixing the input size to the output size, for example). Want to find the edge-reversal of that graph? It'll cost ya.
- isaacfrond 3y agoI'm not sure the new formulation is correct either. It now states. An n-node simple graph (...) then we can encode the graph in polynomial space! But any n-node graph can be encoded in polynomial space. Maybe you mean to encode a 2^n node graph in polynomial space?