4 ms·
Pretty sure "n-node" is a typo and both vertices and edges are 2ⁿ.
by perihelions 4y ago
Pretty sure "n-node" is a typo and both vertices and edges are 2ⁿ.
- hwayne 4y agoNo, it's a dumb mistake, I was thinking of the number of subgraphs of the N-node graph. I'll fix it.
- klyrs 4y 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 4y 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?